Kelner, Jonathan A.; Li, Jerry; Liu, Allen; Sidford, Aaron; Tian, Kevin Matrix Completion in Almost-Verification Time. arXiv:2308.03661 Preprint, arXiv:2308.03661 [cs.LG] (2023). BibTeX Cite \textit{J. A. Kelner} et al., ``Matrix Completion in Almost-Verification Time'', Preprint, arXiv:2308.03661 [cs.LG] (2023) Full Text: arXiv OA License
Gatmiry, Khashayar; Kelner, Jonathan; Vempala, Santosh S. Sampling with Barriers: Faster Mixing via Lewis Weights. arXiv:2303.00480 Preprint, arXiv:2303.00480 [cs.DS] (2023). BibTeX Cite \textit{K. Gatmiry} et al., ``Sampling with Barriers: Faster Mixing via Lewis Weights'', Preprint, arXiv:2303.00480 [cs.DS] (2023) Full Text: arXiv OA License
Kelner, Jonathan A.; Li, Jerry; Liu, Allen; Sidford, Aaron; Tian, Kevin Semi-Random Sparse Recovery in Nearly-Linear Time. arXiv:2203.04002 Preprint, arXiv:2203.04002 [cs.DS] (2022). BibTeX Cite \textit{J. A. Kelner} et al., ``Semi-Random Sparse Recovery in Nearly-Linear Time'', Preprint, arXiv:2203.04002 [cs.DS] (2022) Full Text: arXiv OA License
Kelner, Jonathan; Marsden, Annie; Sharan, Vatsal; Sidford, Aaron; Valiant, Gregory; Yuan, Honglin Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales. arXiv:2111.03137 Preprint, arXiv:2111.03137 [math.OC] (2021). BibTeX Cite \textit{J. Kelner} et al., ``Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales'', Preprint, arXiv:2111.03137 [math.OC] (2021) Full Text: arXiv OA License
Gonçalves, Glauco Estácio; Endo, Patricia Takako; Rodrigues, Moises; Sadok, Djamel H.; Kelner, Judith; Curescu, Calin Resource allocation based on redundancy models for high availability cloud. (English) Zbl 1459.68014 Computing 102, No. 1, 43-63 (2020). MSC: 68M11 68M20 PDFBibTeX XMLCite \textit{G. E. Gonçalves} et al., Computing 102, No. 1, 43--63 (2020; Zbl 1459.68014) Full Text: DOI
Barak, Boaz; Hopkins, Samuel; Kelner, Jonathan; Kothari, Pravesh K.; Moitra, Ankur; Potechin, Aaron A nearly tight sum-of-squares lower bound for the planted clique problem. (English) Zbl 1421.68056 SIAM J. Comput. 48, No. 2, 687-735 (2019). MSC: 68Q17 05C69 05C80 68Q25 90C22 PDFBibTeX XMLCite \textit{B. Barak} et al., SIAM J. Comput. 48, No. 2, 687--735 (2019; Zbl 1421.68056) Full Text: DOI arXiv
Cohen, Michael B.; Kelner, Jonathan; Peebles, John; Peng, Richard; Rao, Anup B.; Sidford, Aaron; Vladu, Adrian 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). MSC: 60J10 05C20 05C50 05C85 65F08 68W40 PDFBibTeX XMLCite \textit{M. B. Cohen} et al., in: 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). 410--419 (2017; Zbl 1370.60115) Full Text: DOI arXiv
Censor-Hillel, Keren; Haeupler, Bernhard; Kelner, Jonathan; Maymounkov, Petar Rumor spreading with no dependence on conductance. (English) Zbl 1359.68024 SIAM J. Comput. 46, No. 1, 58-79 (2017). MSC: 68M14 68M10 68W15 PDFBibTeX XMLCite \textit{K. Censor-Hillel} et al., SIAM J. Comput. 46, No. 1, 58--79 (2017; Zbl 1359.68024) Full Text: DOI
Barak, Boaz; Kelner, Jonathan A.; Steurer, David 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 \textit{B. Barak} et al., in: 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). 143--151 (2015; Zbl 1321.68396) Full Text: DOI arXiv
Kelner, Jonathan A.; Lee, Yin Tat; Orecchia, Lorenzo; Sidford, Aaron 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). MSC: 05C85 05C21 68W25 68W40 90C35 PDFBibTeX XMLCite \textit{J. A. Kelner} et al., in: 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; Zbl 1423.05177) Full Text: DOI arXiv Link
Barak, Boaz; Kelner, Jonathan A.; Steurer, David 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). MSC: 90C22 68Q12 68Q25 68W25 PDFBibTeX XMLCite \textit{B. Barak} et al., in: 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). 31--40 (2014; Zbl 1315.90028) Full Text: DOI arXiv
Kelner, Jonathan A.; Orecchia, Lorenzo; Sidford, Aaron; Zhu, Zeyuan Allen 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). MSC: 68Q17 05C50 65F05 68R10 PDFBibTeX XMLCite \textit{J. A. Kelner} et al., in: 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). 911--920 (2013; Zbl 1293.68145) Full Text: DOI arXiv
Kelner, Jonathan A.; Levin, Alex Spectral sparsification in the semi-streaming setting. (English) Zbl 1273.05222 Theory Comput. Syst. 53, No. 2, 243-262 (2013). MSC: 05C85 68R10 68P05 68W20 PDFBibTeX XMLCite \textit{J. A. Kelner} and \textit{A. Levin}, Theory Comput. Syst. 53, No. 2, 243--262 (2013; Zbl 1273.05222) Full Text: DOI Link
Anandkumar, Animashree; Hassidim, Avinatan; Kelner, Jonathan Topology discovery of sparse random graphs with few participants. (English) Zbl 1270.05088 Random Struct. Algorithms 43, No. 1, 16-48 (2013). MSC: 05C80 05C42 05C10 PDFBibTeX XMLCite \textit{A. Anandkumar} et al., Random Struct. Algorithms 43, No. 1, 16--48 (2013; Zbl 1270.05088) Full Text: DOI Link
Zhu, Zeyuan Allen; Misailovic, Sasa; Kelner, Jonathan A.; Rinard, Martin 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 \textit{Z. A. Zhu} et al., in: 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). 441--454 (2012; Zbl 1321.68208) Full Text: DOI
Censor-Hillel, Keren; Haeupler, Bernhard; Kelner, Jonathan; Maymounkov, Petar 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). MSC: 68M12 68M10 68M14 68Q85 PDFBibTeX XMLCite \textit{K. Censor-Hillel} et al., in: 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). 961--970 (2012; Zbl 1286.68017) Full Text: DOI
Barak, Boaz; Brandão, Fernando G. S. L.; Harrow, Aram W.; Kelner, Jonathan; Steurer, David; Zhou, Yuan 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). MSC: 68Q17 47A30 81P45 90C22 94A24 PDFBibTeX XMLCite \textit{B. Barak} et al., in: 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). 307--326 (2012; Zbl 1286.68176) Full Text: DOI arXiv
Kelner, Jonathan A.; Miller, Gary L.; Peng, Richard 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 \textit{J. A. Kelner} et al., in: 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). 1--18 (2012; Zbl 1286.05062) Full Text: DOI arXiv
Christiano, Paul; Kelner, Jonathan A.; Madry, Aleksander; Spielman, Daniel A.; Teng, Shang-Hua 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). MSC: 94C15 05C21 68W25 90B10 90C35 PDFBibTeX XMLCite \textit{P. Christiano} et al., in: 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). 273--282 (2011; Zbl 1288.94127) Full Text: DOI arXiv Link
Kelner, Jonathan A.; Lee, James R.; Price, Gregory N.; Teng, Shang-Hua Metric uniformization and spectral bounds for graphs. (English) Zbl 1229.05094 Geom. Funct. Anal. 21, No. 5, 1117-1143 (2011). MSC: 05C10 05C50 51F99 52C26 58A99 PDFBibTeX XMLCite \textit{J. A. Kelner} et al., Geom. Funct. Anal. 21, No. 5, 1117--1143 (2011; Zbl 1229.05094) Full Text: DOI arXiv
Kelner, Jonathan A.; Levin, Alex 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). MSC: 05C85 68P05 05C50 05C60 05C70 68R10 PDFBibTeX XMLCite \textit{J. A. Kelner} and \textit{A. Levin}, LIPIcs -- Leibniz Int. Proc. Inform. 9, 440--451 (2011; Zbl 1229.05257) Full Text: DOI Link
Goemans, Michel X.; Kelner, Jonathan A. The mathematical work of Daniel Spielman. (English) Zbl 1228.01038 Notices Am. Math. Soc. 58, No. 9, 1288-1290 (2011). MSC: 01A70 PDFBibTeX XMLCite \textit{M. X. Goemans} and \textit{J. A. Kelner}, Notices Am. Math. Soc. 58, No. 9, 1288--1290 (2011; Zbl 1228.01038)
Kelner, Jonathan; Maymounkov, Petar Electric routing and concurrent flow cutting. (English) Zbl 1221.68172 Theor. Comput. Sci. 412, No. 32, 4123-4135 (2011). MSC: 68R10 68M11 PDFBibTeX XMLCite \textit{J. Kelner} and \textit{P. Maymounkov}, Theor. Comput. Sci. 412, No. 32, 4123--4135 (2011; Zbl 1221.68172) Full Text: DOI
Sedransk, Nell; Young, Linda J.; Kelner, Katrina L.; Moffitt, Robert A.; Thakar, Ani; Raddick, Jordan; Ungvarsky, Edward J.; Carlson, Richard W.; Apweiler, Rolf; Cox, Lawrence H.; Nolan, Deborah; Soper, Keith; Spiegelman, Cliff Make research data public? – Not always so simple: A dialogue for statisticians and science editors. (English) Zbl 1328.62041 Stat. Sci. 25, No. 1, 41-50 (2010). MSC: 62A01 01A65 01A80 62-07 62-03 62Pxx PDFBibTeX XMLCite \textit{N. Sedransk} et al., Stat. Sci. 25, No. 1, 41--50 (2010; Zbl 1328.62041) Full Text: DOI arXiv Euclid
Kelner, Jonathan A.; Lee, James R.; Price, Gregory N.; Teng, Shang-Hua 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 \textit{J. A. Kelner} et al., in: 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. 735--744 (2009; Zbl 1292.05172) Full Text: DOI
Kelner, Jonathan A.; Madry, Aleksander 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 \textit{J. A. Kelner} and \textit{A. Madry}, in: 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. 13--21 (2009; Zbl 1292.05248) Full Text: DOI
Hassidim, Avinatan; Kelner, Jonathan A.; Nguyen, Huy N.; Onak, Krzysztof 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). MSC: 68R10 05C85 68W20 68W25 PDFBibTeX XMLCite \textit{A. Hassidim} et al., in: 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. 22--31 (2009; Zbl 1292.68126) Full Text: DOI
Kelner, Jonathan; Maymounkov, Petar 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 \textit{J. Kelner} and \textit{P. Maymounkov}, Lect. Notes Comput. Sci. 5878, 792--801 (2009; Zbl 1273.68057) Full Text: DOI Link
Fernandes, Stênio; Kamienski, Carlos; Kelner, Judith; Mariz, Dênio; Sadok, Djamel A stratified traffic sampling methodology for seeing the big picture. (English) Zbl 1162.68322 Comput. Netw. 52, No. 14, 2677-2689 (2008). MSC: 68M10 PDFBibTeX XMLCite \textit{S. Fernandes} et al., Comput. Netw. 52, No. 14, 2677--2689 (2008; Zbl 1162.68322) Full Text: DOI
Kelner, Jonathan A.; Spielman, Daniel A. 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 \textit{J. A. Kelner} and \textit{D. A. Spielman}, in: 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. 51--60 (2006; Zbl 1301.68262) Full Text: DOI
Nikolova, Evdokia; Kelner, Jonathan A.; Brand, Matthew; Mitzenmacher, Michael 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 \textit{E. Nikolova} et al., Lect. Notes Comput. Sci. 4168, 552--563 (2006; Zbl 1131.05317) Full Text: DOI
Kelner, Jonathan A. Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. (English) Zbl 1096.05048 SIAM J. Comput. 35, No. 4, 882-902 (2006). MSC: 05C85 68R10 68W40 68Q25 68W05 PDFBibTeX XMLCite \textit{J. A. Kelner}, SIAM J. Comput. 35, No. 4, 882--902 (2006; Zbl 1096.05048) Full Text: DOI
Kelner, Jonathan A. 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). MSC: 05C85 05C10 05C40 05C50 68R10 68W40 68Q25 68W05 PDFBibTeX XMLCite \textit{J. A. Kelner}, in: 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. 455--464 (2004; Zbl 1192.05162) Full Text: DOI Link
Goyal, Vivek K.; Kelner, Jonathan A.; Kovačević, Jelena Multiple description vector quantization with a coarse lattice. (English) Zbl 1071.94524 IEEE Trans. Inf. Theory 48, No. 3, 781-788 (2002). MSC: 94A24 PDFBibTeX XMLCite \textit{V. K. Goyal} et al., IEEE Trans. Inf. Theory 48, No. 3, 781--788 (2002; Zbl 1071.94524) Full Text: DOI Link
Goyal, Vivek K.; Kovačević, Jelena; Kelner, Jonathan A. Quantized frame expansions with erasures. (English) Zbl 0992.94009 Appl. Comput. Harmon. Anal. 10, No. 3, 203-233 (2001). MSC: 94A12 42C15 94A29 PDFBibTeX XMLCite \textit{V. K. Goyal} et al., Appl. Comput. Harmon. Anal. 10, No. 3, 203--233 (2001; Zbl 0992.94009) Full Text: DOI
Sadok, Djamel F. H.; de M. Cordeiro, Carlos; Kelner, Judith Performance analysis of a multicast protocol for wireless environments. (English) Zbl 1036.68503 Simulation 75, No. 1, 32-42 (2000). MSC: 68M20 68M12 68U20 PDFBibTeX XML Full Text: DOI