×

Found 36 Documents (Results 1–36)

Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs. (English) Zbl 1370.60115

Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 410-419 (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Dictionary learning and tensor decomposition via the sum-of-squares method. (English) Zbl 1321.68396

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 143-151 (2015).
MSC:  68T05 90C22
PDFBibTeX XMLCite
Full Text: DOI arXiv

An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. (English) Zbl 1423.05177

Chekuri, Chandra (ed.), Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 217-226 (2014).
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Rounding sum-of-squares relaxations. (English) Zbl 1315.90028

Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 31-40 (2014).
PDFBibTeX XMLCite
Full Text: DOI arXiv

A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. (English) Zbl 1293.68145

Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 911-920 (2013).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Randomized accuracy-aware program transformations for efficient approximate computations. (English) Zbl 1321.68208

Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’12, Philadelphia, PA, USA, January 22–28, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1083-3). 441-454 (2012).
MSC:  68N30 68Q05 68W20 68W25
PDFBibTeX XMLCite
Full Text: DOI

Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. (English) Zbl 1286.68017

Karloff, Howard J. (ed.) et al., Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19–22, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1245-5). 961-970 (2012).
PDFBibTeX XMLCite
Full Text: DOI

Hypercontractivity, sum-of-squares proofs, and their applications. (English) Zbl 1286.68176

Karloff, Howard J. (ed.) et al., Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19–22, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1245-5). 307-326 (2012).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Faster approximate multicommodity flow using quadratically coupled flows. (English) Zbl 1286.05062

Karloff, Howard J. (ed.) et al., Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19–22, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1245-5). 1-18 (2012).
MSC:  05C21 05C50
PDFBibTeX XMLCite
Full Text: DOI arXiv

Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. (English) Zbl 1288.94127

Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 273-282 (2011).
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Spectral sparsification in the semi-streaming setting. (English) Zbl 1229.05257

Schwentick, Thomas (ed.) et al., STACS 2011. 28th international symposium on theoretical aspects of computer science, Dortmund, Germany, March 10–12, 2011. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-25-5). LIPIcs – Leibniz International Proceedings in Informatics 9, 440-451, electronic only (2011).
PDFBibTeX XMLCite
Full Text: DOI Link

Higher eigenvalues of graphs. (English) Zbl 1292.05172

2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24–27, 2009. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-3850-1; 978-1-4244-5116-6/ebook). 735-744 (2009).
MSC:  05C50
PDFBibTeX XMLCite
Full Text: DOI

Faster generation of random spanning trees. (English) Zbl 1292.05248

2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24–27, 2009. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-3850-1; 978-1-4244-5116-6/ebook). 13-21 (2009).
MSC:  05C85 68R10 68Q87
PDFBibTeX XMLCite
Full Text: DOI

Local graph partitions for approximation and testing. (English) Zbl 1292.68126

2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24–27, 2009. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-3850-1; 978-1-4244-5116-6/ebook). 22-31 (2009).
PDFBibTeX XMLCite
Full Text: DOI

Electric routing and concurrent flow cutting. (English) Zbl 1273.68057

Dong, Yingfei (ed.) et al., Algorithms and computation. 20th international symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16–18, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-10630-9/pbk). Lecture Notes in Computer Science 5878, 792-801 (2009).
MSC:  68M11 68M14 68R10
PDFBibTeX XMLCite
Full Text: DOI Link

A randomized polynomial-time simplex algorithm for linear programming. (English) Zbl 1301.68262

Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 51-60 (2006).
MSC:  68W20 90C05 68W40
PDFBibTeX XMLCite
Full Text: DOI

Stochastic shortest paths via quasi-convex maximization. (English) Zbl 1131.05317

Azar, Yossi (ed.) et al., Algorithms – ESA 2006. 14th annual European symposium, Zurich, Switzerland, September 11–13, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-38875-3/pbk). Lecture Notes in Computer Science 4168, 552-563 (2006).
MSC:  05C85 90C35 90C59
PDFBibTeX XMLCite
Full Text: DOI

Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. (English) Zbl 1192.05162

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 455-464, electronic only (2004).
PDFBibTeX XMLCite
Full Text: DOI Link

Filter Results by …

Database

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

Biographic Reference

all top 3

Software