Filtser, Arnold; Neiman, Ofer Light spanners for high dimensional norms via stochastic decompositions. (English) Zbl 07596609 Algorithmica 84, No. 10, 2987-3007 (2022). MSC: 68Wxx 05Cxx PDFBibTeX XMLCite \textit{A. Filtser} and \textit{O. Neiman}, Algorithmica 84, No. 10, 2987--3007 (2022; Zbl 07596609) Full Text: DOI
Henzinger, Monika; Krinninger, Sebastian; Nanongkai, Danupon A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. (English) Zbl 1466.68085 SIAM J. Comput. 50, No. 3, STOC16-98-STOC16-137 (2021). MSC: 68W25 05C85 68W15 68W20 PDFBibTeX XMLCite \textit{M. Henzinger} et al., SIAM J. Comput. 50, No. 3, STOC16--98-STOC16--137 (2021; Zbl 1466.68085) Full Text: DOI
Filtser, Arnold; Solomon, Shay The greedy spanner is existentially optimal. (English) Zbl 1437.05221 SIAM J. Comput. 49, No. 2, 429-447 (2020). MSC: 05C85 68W40 68U05 PDFBibTeX XMLCite \textit{A. Filtser} and \textit{S. Solomon}, SIAM J. Comput. 49, No. 2, 429--447 (2020; Zbl 1437.05221) Full Text: DOI
Filtser, Arnold; Neiman, Ofer Light spanners for high dimensional norms via stochastic decompositions. (English) Zbl 1524.68407 Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 29, 15 p. (2018). MSC: 68U05 54E35 68R10 PDFBibTeX XMLCite \textit{A. Filtser} and \textit{O. Neiman}, LIPIcs -- Leibniz Int. Proc. Inform. 112, Article 29, 15 p. (2018; Zbl 1524.68407) Full Text: DOI arXiv
Kobayashi, Yusuke NP-hardness and fixed-parameter tractability of the minimum spanner problem. (English) Zbl 1401.68098 Theor. Comput. Sci. 746, 88-97 (2018). MSC: 68Q17 05C85 68R10 PDFBibTeX XMLCite \textit{Y. Kobayashi}, Theor. Comput. Sci. 746, 88--97 (2018; Zbl 1401.68098) Full Text: DOI Link
Zhu, Chun Jiang; Lam, Kam-Yiu Deterministic improved round-trip spanners. (English) Zbl 1420.68160 Inf. Process. Lett. 129, 57-60 (2018). MSC: 68R10 05C85 PDFBibTeX XMLCite \textit{C. J. Zhu} and \textit{K.-Y. Lam}, Inf. Process. Lett. 129, 57--60 (2018; Zbl 1420.68160) Full Text: DOI
Zhu, Chun Jiang; Lam, Kam-Yiu Source-wise round-trip spanners. (English) Zbl 1416.05272 Inf. Process. Lett. 124, 42-45 (2017). MSC: 05C85 05C12 PDFBibTeX XMLCite \textit{C. J. Zhu} and \textit{K.-Y. Lam}, Inf. Process. Lett. 124, 42--45 (2017; Zbl 1416.05272) Full Text: DOI
Henzinger, Monika; Krinninger, Sebastian; Nanongkai, Danupon Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization. (English) Zbl 1339.05387 SIAM J. Comput. 45, No. 3, 947-1006 (2016). MSC: 05C85 05C38 05C12 68W20 68W05 68W40 PDFBibTeX XMLCite \textit{M. Henzinger} et al., SIAM J. Comput. 45, No. 3, 947--1006 (2016; Zbl 1339.05387) Full Text: DOI arXiv
Basavanagoud, B.; Veeragoudar, Jaishri B. Bounds on the spanner-sum of torus. (English) Zbl 1511.05062 J. Discrete Math. Sci. Cryptography 18, No. 1-2, 147-155 (2015). MSC: 05C12 05C05 05C82 68R10 PDFBibTeX XMLCite \textit{B. Basavanagoud} and \textit{J. B. Veeragoudar}, J. Discrete Math. Sci. Cryptography 18, No. 1--2, 147--155 (2015; Zbl 1511.05062) Full Text: DOI
Chan, T.-H. Hubert; Li, Mingfei; Ning, Li; Solomon, Shay New doubling spanners: better and simpler. (English) Zbl 1353.05043 SIAM J. Comput. 44, No. 1, 37-53 (2015). MSC: 05C12 PDFBibTeX XMLCite \textit{T. H. H. Chan} et al., SIAM J. Comput. 44, No. 1, 37--53 (2015; Zbl 1353.05043) Full Text: DOI Link
Korula, Nitish; Mirrokni, Vahab; Zadimoghaddam, Morteza Online submodular welfare maximization: greedy beats 1/2 in random order. (English) Zbl 1322.91031 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). 889-898 (2015). MSC: 91B15 91B26 91B32 90C90 68W27 PDFBibTeX XMLCite \textit{N. Korula} 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). 889--898 (2015; Zbl 1322.91031) Full Text: DOI
Kesselheim, Thomas; Kleinberg, Robert; Niazadeh, Rad Secretary problems with non-uniform arrival order. (English) Zbl 1321.68516 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). 879-888 (2015). MSC: 68W27 68Q25 PDFBibTeX XMLCite \textit{T. Kesselheim} 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). 879--888 (2015; Zbl 1321.68516) Full Text: DOI arXiv
Gupta, Anupam; Kumar, Amit Greedy algorithms for Steiner forest. (English) Zbl 1321.68504 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). 871-878 (2015). MSC: 68W25 05C05 05C21 68Q25 68T20 PDFBibTeX XMLCite \textit{A. Gupta} and \textit{A. Kumar}, 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). 871--878 (2015; Zbl 1321.68504) Full Text: DOI arXiv
Nikolov, Aleksandar Randomized rounding for the largest simplex problem. (English) Zbl 1321.68319 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). 861-870 (2015). MSC: 68Q25 68U05 68W25 90C25 PDFBibTeX XMLCite \textit{A. Nikolov}, 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). 861--870 (2015; Zbl 1321.68319) Full Text: DOI arXiv
Bansal, Nikhil; Kulkarni, Janardhan Minimizing flow-time on unrelated machines. (English) Zbl 1321.68113 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). 851-860 (2015). MSC: 68M20 68W25 90C05 PDFBibTeX XMLCite \textit{N. Bansal} and \textit{J. Kulkarni}, 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). 851--860 (2015; Zbl 1321.68113) Full Text: DOI arXiv
Fox, Kyle; Klein, Philip N.; Mozes, Shay A polynomial-time bicriteria approximation scheme for planar bisection. (English) Zbl 1321.68501 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). 841-850 (2015). MSC: 68W25 05C10 05C22 05C70 05C85 PDFBibTeX XMLCite \textit{K. Fox} 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). 841--850 (2015; Zbl 1321.68501) Full Text: DOI arXiv
Schulman, Leonard J.; Sinclair, Alistair Analysis of a classical matrix preconditioning algorithm. (English) Zbl 1321.65045 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). 831-840 (2015). MSC: 65F08 PDFBibTeX XMLCite \textit{L. J. Schulman} and \textit{A. Sinclair}, 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). 831--840 (2015; Zbl 1321.65045) Full Text: DOI arXiv Link
Moitra, Ankur Super-resolution, extremal functions and the condition number of Vandermonde matrices. (English) Zbl 1321.68421 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). 821-830 (2015). MSC: 68T45 68T05 68U10 PDFBibTeX XMLCite \textit{A. Moitra}, 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). 821--830 (2015; Zbl 1321.68421) Full Text: DOI arXiv
Christiani, Tobias; Pagh, Rasmus; Thorup, Mikkel From independence to expansion and back again. (English) Zbl 1321.68219 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). 813-820 (2015). MSC: 68P05 68Q17 68R10 PDFBibTeX XMLCite \textit{T. Christiani} 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). 813--820 (2015; Zbl 1321.68219) Full Text: DOI arXiv
Larsen, Kasper Green; Nelson, Jelani; Nguyên, Huy L. Time lower bounds for nonadaptive turnstile streaming algorithms. (English) Zbl 1321.68286 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). 803-812 (2015). MSC: 68Q17 68W05 68W20 PDFBibTeX XMLCite \textit{K. G. Larsen} 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). 803--812 (2015; Zbl 1321.68286) Full Text: DOI arXiv
Andoni, Alexandr; Razenshteyn, Ilya Optimal data-dependent hashing for approximate near neighbors. (English) Zbl 1321.68212 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). 793-801 (2015). MSC: 68P05 68Q17 68T05 68W25 PDFBibTeX XMLCite \textit{A. Andoni} and \textit{I. Razenshteyn}, 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). 793--801 (2015; Zbl 1321.68212) Full Text: DOI arXiv
Mulzer, Wolfgang; Nguyên, Huy L.; Seiferth, Paul; Stein, Yannik Approximate \(k\)-flat nearest neighbor search. (English) Zbl 1321.68416 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). 783-792 (2015). MSC: 68T20 68P05 68W25 PDFBibTeX XMLCite \textit{W. Mulzer} 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). 783--792 (2015; Zbl 1321.68416) Full Text: DOI arXiv
Bresler, Guy Efficiently learning Ising models on arbitrary graphs (extended abstract). (English) Zbl 1321.68397 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). 771-782 (2015). MSC: 68T05 82B20 82C20 PDFBibTeX XMLCite \textit{G. Bresler}, 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). 771--782 (2015; Zbl 1321.68397) Full Text: DOI arXiv
Ge, Rong; Huang, Qingqing; Kakade, Sham M. Learning mixtures of Gaussians in high dimensions. (English) Zbl 1321.68403 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). 761-770 (2015). MSC: 68T05 PDFBibTeX XMLCite \textit{R. Ge} 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). 761--770 (2015; Zbl 1321.68403) Full Text: DOI arXiv
Hardt, Moritz; Price, Eric Tight bounds for learning a mixture of two Gaussians (extended abstract). (English) Zbl 1321.68405 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). 753-760 (2015). MSC: 68T05 62F12 PDFBibTeX XMLCite \textit{M. Hardt} and \textit{E. Price}, 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). 753--760 (2015; Zbl 1321.68405) Full Text: DOI arXiv
Li, Jian; Rabani, Yuval; Schulman, Leonard J.; Swamy, Chaitanya Learning arbitrary statistical mixtures of discrete distributions. (English) Zbl 1321.68407 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). 743-752 (2015). MSC: 68T05 68W20 PDFBibTeX XMLCite \textit{J. Li} 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). 743--752 (2015; Zbl 1321.68407) Full Text: DOI arXiv Link
Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract). (English) Zbl 1321.68426 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). 733-742 (2015). MSC: 68W20 11Y16 94A60 PDFBibTeX XMLCite \textit{D. Aggarwal} 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). 733--742 (2015; Zbl 1321.68426) Full Text: DOI arXiv
Czumaj, Artur; Peng, Pan; Sohler, Christian Testing cluster structure of graphs. (English) Zbl 1321.68489 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). 723-732 (2015). MSC: 68W20 05C81 68Q17 68Q25 PDFBibTeX XMLCite \textit{A. Czumaj} 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). 723--732 (2015; Zbl 1321.68489) Full Text: DOI arXiv
Louis, Anand Hypergraph Markov operators, eigenvalues and approximation algorithms. (English) Zbl 1321.05174 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). 713-722 (2015). MSC: 05C65 05C50 68W25 PDFBibTeX XMLCite \textit{A. Louis}, 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). 713--722 (2015; Zbl 1321.05174) Full Text: DOI arXiv
Czumaj, Artur Random permutations using switching networks. (English) Zbl 1321.65007 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). 703-712 (2015). MSC: 65C10 94C10 PDFBibTeX XMLCite \textit{A. Czumaj}, 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). 703--712 (2015; Zbl 1321.65007) Full Text: DOI
Sun, Xiaorui; Wilmes, John Faster canonical forms for primitive coherent configurations (extended abstract). (English) Zbl 1321.05164 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). 693-702 (2015). MSC: 05C60 05C15 05C20 05C25 05E30 20B20 68Q25 PDFBibTeX XMLCite \textit{X. Sun} and \textit{J. Wilmes}, 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). 693--702 (2015; Zbl 1321.05164) Full Text: DOI arXiv
Grohe, Martin; Schweitzer, Pascal Computing with tangles. (English) Zbl 1321.05264 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). 683-692 (2015). MSC: 05C85 05C40 05C69 05C83 68P05 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{P. Schweitzer}, 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). 683--692 (2015; Zbl 1321.05264) Full Text: DOI arXiv
Kawarabayashi, Ken-ichi; Sidiropoulos, Anastasios Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract). (English) Zbl 1321.05063 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). 675-682 (2015). MSC: 05C10 68W25 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{A. Sidiropoulos}, 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). 675--682 (2015; Zbl 1321.05063) Full Text: DOI arXiv
Kawarabayashi, Ken-ichi; Thorup, Mikkel Deterministic global minimum cut of a simple graph in near-linear time. (English) Zbl 1321.05268 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). 665-674 (2015). MSC: 05C85 05C40 05C70 68Q25 68R10 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{M. Thorup}, 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). 665--674 (2015; Zbl 1321.05268) Full Text: DOI
Kawarabayashi, Ken-ichi; Kreutzer, Stephan The directed grid theorem. (English) Zbl 1321.05249 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). 655-664 (2015). MSC: 05C83 05C75 05C78 05C20 68Q17 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{S. Kreutzer}, 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). 655--664 (2015; Zbl 1321.05249) Full Text: DOI arXiv
Chuzhoy, Julia Excluded grid theorem: improved and simplified. (English) Zbl 1321.05248 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). 645-654 (2015). MSC: 05C83 05C75 05C78 68Q17 68Q25 PDFBibTeX XMLCite \textit{J. Chuzhoy}, 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). 645--654 (2015; Zbl 1321.05248) Full Text: DOI
Halldorsson, Magnus M.; Tonoyan, Tigran How well can graphs represent wireless interference? (English) Zbl 1321.68023 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). 635-644 (2015). MSC: 68M10 68M12 68M20 68R10 PDFBibTeX XMLCite \textit{M. M. Halldorsson} and \textit{T. Tonoyan}, 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). 635--644 (2015; Zbl 1321.68023) Full Text: DOI arXiv
Alstrup, Stephen; Kaplan, Haim; Thorup, Mikkel; Zwick, Uri Adjacency labeling schemes and induced-universal graphs. (English) Zbl 1321.05226 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). 625-634 (2015). MSC: 05C78 05C20 68Q17 PDFBibTeX XMLCite \textit{S. Alstrup} 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). 625--634 (2015; Zbl 1321.05226) Full Text: DOI arXiv
Giakkoupis, George; Helmi, Maryam; Higham, Lisa; Woelfel, Philipp Test-and-set in optimal space. (English) Zbl 1321.68105 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). 615-623 (2015). MSC: 68M15 68M10 68Q25 PDFBibTeX XMLCite \textit{G. Giakkoupis} 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). 615--623 (2015; Zbl 1321.68105) Full Text: DOI
Abraham, Ittai; Dolev, Danny Byzantine agreement with optimal early stopping, optimal resilience and polynomial complexity. (English) Zbl 1321.68096 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). 605-614 (2015). MSC: 68M15 68M12 68M14 PDFBibTeX XMLCite \textit{I. Abraham} and \textit{D. Dolev}, 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). 605--614 (2015; Zbl 1321.68096) Full Text: DOI arXiv
Alwen, Joël; Serbinenko, Vladimir High parallel complexity graphs and memory-hard functions. (English) Zbl 1321.68374 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). 595-603 (2015). MSC: 68R10 94A60 68Q05 68Q10 68Q17 68W10 PDFBibTeX XMLCite \textit{J. Alwen} and \textit{V. Serbinenko}, 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). 595--603 (2015; Zbl 1321.68374) Full Text: DOI
Ambainis, Andris; Filmus, Yuval; Le Gall, François Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract). (English) Zbl 1321.65063 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). 585-593 (2015). MSC: 65F30 68Q17 68Q25 PDFBibTeX XMLCite \textit{A. Ambainis} 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). 585--593 (2015; Zbl 1321.65063) Full Text: DOI arXiv
Dvir, Zeev; Gopi, Sivakanth 2-server PIR with sub-polynomial communication. (English) Zbl 1321.68253 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). 577-584 (2015). MSC: 68P20 94B35 PDFBibTeX XMLCite \textit{Z. Dvir} and \textit{S. Gopi}, 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). 577--584 (2015; Zbl 1321.68253) Full Text: DOI arXiv
Lee, James R.; Raghavendra, Prasad; Steurer, David Lower bounds on the size of semidefinite programming relaxations. (English) Zbl 1321.90099 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). 567-576 (2015). MSC: 90C22 68Q17 PDFBibTeX XMLCite \textit{J. R. Lee} 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). 567--576 (2015; Zbl 1321.90099) Full Text: DOI arXiv
Ganor, Anat; Kol, Gillat; Raz, Ran Exponential separation of information and communication for Boolean functions (extended abstract). (English) Zbl 1321.68311 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). 557-566 (2015). MSC: 68Q25 68P30 PDFBibTeX XMLCite \textit{A. Ganor} 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). 557--566 (2015; Zbl 1321.68311) Full Text: DOI
Liu, Jingcheng; Lu, Pinyan FPTAS for #BIS with degree bounds on one side. (English) Zbl 1321.05185 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). 549-556 (2015). MSC: 05C69 68Q25 68W25 PDFBibTeX XMLCite \textit{J. Liu} and \textit{P. Lu}, 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). 549--556 (2015; Zbl 1321.05185) Full Text: DOI arXiv
Cousins, Benjamin; Vempala, Santosh Bypassing KLS: Gaussian cooling and an \(O^\ast(n^3)\) volume algorithm. (English) Zbl 1321.68434 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). 539-548 (2015). MSC: 68U05 68W20 68Q25 PDFBibTeX XMLCite \textit{B. Cousins} and \textit{S. Vempala}, 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). 539--548 (2015; Zbl 1321.68434) Full Text: DOI arXiv
O’Donnell, Ryan; Wright, John Quantum spectrum testing. (English) Zbl 1321.68273 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). 529-538 (2015). MSC: 68Q12 68Q25 68W20 PDFBibTeX XMLCite \textit{R. O'Donnell} and \textit{J. Wright}, 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). 529--538 (2015; Zbl 1321.68273) Full Text: DOI arXiv
Chen, Xi; De, Anindya; Servedio, Rocco A.; Tan, Li-Yang Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries. (English) Zbl 1321.68300 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). 519-528 (2015). MSC: 68Q25 68Q17 68W20 PDFBibTeX XMLCite \textit{X. Chen} 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). 519--528 (2015; Zbl 1321.68300) Full Text: DOI arXiv
Abdullah, Amirali; Venkatasubramanian, Suresh A directed isoperimetric inequality with application to Bregman near neighbor lower bounds. (English) Zbl 1321.68210 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). 509-518 (2015). MSC: 68P05 68Q17 94A17 PDFBibTeX XMLCite \textit{A. Abdullah} and \textit{S. Venkatasubramanian}, 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). 509--518 (2015; Zbl 1321.68210) Full Text: DOI arXiv
Bourgain, Jean; Dirksen, Sjoerd; Nelson, Jelani Toward a unified theory of sparse dimensionality reduction in Euclidean space. (English) Zbl 1321.68431 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). 499-508 (2015). MSC: 68U05 68T05 68W20 PDFBibTeX XMLCite \textit{J. Bourgain} 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). 499--508 (2015; Zbl 1321.68431) Full Text: DOI arXiv
Elkin, Michael; Filtser, Arnold; Neiman, Ofer Prioritized metric structures and embedding. (English) Zbl 1321.68222 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). 489-498 (2015). MSC: 68P05 05C22 68U05 PDFBibTeX XMLCite \textit{M. Elkin} 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). 489--498 (2015; Zbl 1321.68222) Full Text: DOI arXiv
Andoni, Alexandr; Krauthgamer, Robert; Razenshteyn, Ilya Sketching and embedding are equivalent for norms. (English) Zbl 1321.68428 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). 479-488 (2015). MSC: 68U05 PDFBibTeX XMLCite \textit{A. Andoni} 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). 479--488 (2015; Zbl 1321.68428) Full Text: DOI arXiv
Gorbunov, Sergey; Vaikuntanathan, Vinod; Wichs, Daniel Leveled fully homomorphic signatures from standard lattices. (English) Zbl 1321.94062 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). 469-477 (2015). MSC: 94A60 94A62 PDFBibTeX XMLCite \textit{S. Gorbunov} 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). 469--477 (2015; Zbl 1321.94062) Full Text: DOI Link
Aggarwal, Divesh; Dodis, Yevgeniy; Kazana, Tomasz; Obremski, Maciej Non-malleable reductions and applications. (English) Zbl 1321.94139 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). 459-468 (2015). MSC: 94B60 94A60 PDFBibTeX XMLCite \textit{D. Aggarwal} 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). 459--468 (2015; Zbl 1321.94139) Full Text: DOI
Garg, Sanjam; Lu, Steve; Ostrovsky, Rafail; Scafuro, Alessandra Garbled RAM from one-way functions. (English) Zbl 1321.94061 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). 449-458 (2015). MSC: 94A60 PDFBibTeX XMLCite \textit{S. Garg} 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). 449--458 (2015; Zbl 1321.94061) Full Text: DOI
Bitansky, Nir; Garg, Sanjam; Lin, Huijia; Pass, Rafael; Telang, Sidharth Succinct randomized encodings and their applications. (English) Zbl 1321.94041 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). 439-448 (2015). MSC: 94A60 68W20 PDFBibTeX XMLCite \textit{N. Bitansky} 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). 439--448 (2015; Zbl 1321.94041) Full Text: DOI
Canetti, Ran; Holmgren, Justin; Jain, Abhishek; Vaikuntanathan, Vinod Succinct garbling and indistinguishability obfuscation for RAM programs. (English) Zbl 1321.94050 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). 429-437 (2015). MSC: 94A60 PDFBibTeX XMLCite \textit{R. Canetti} 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). 429--437 (2015; Zbl 1321.94050) Full Text: DOI
Koppula, Venkata; Lewko, Allison Bishop; Waters, Brent Indistinguishability obfuscation for Turing machines with unbounded memory. (English) Zbl 1321.94069 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). 419-428 (2015). MSC: 94A60 68Q05 PDFBibTeX XMLCite \textit{V. Koppula} 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). 419--428 (2015; Zbl 1321.94069) Full Text: DOI
Rubinstein, Aviad Inapproximability of Nash equilibrium. (English) Zbl 1321.68320 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). 409-418 (2015). MSC: 68Q25 68W25 91A10 91B52 PDFBibTeX XMLCite \textit{A. Rubinstein}, 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). 409--418 (2015; Zbl 1321.68320) Full Text: DOI arXiv
Daniely, Amit; Schapira, Michael; Shahaf, Gal Inapproximability of truthful mechanisms via generalizations of the VC dimension. (English) Zbl 1321.68303 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). 401-408 (2015). MSC: 68Q25 68Q17 91B26 PDFBibTeX XMLCite \textit{A. Daniely} 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). 401--408 (2015; Zbl 1321.68303) Full Text: DOI arXiv
Lee, Euiwoong Hardness of graph pricing through generalized Max-Dicut. (English) Zbl 1321.68287 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). 391-399 (2015). MSC: 68Q17 05C22 68Q25 68W25 PDFBibTeX XMLCite \textit{E. Lee}, 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). 391--399 (2015; Zbl 1321.68287) Full Text: DOI arXiv
Chen, Xi; Durfee, David; Orfanou, Anthi On the complexity of Nash equilibria in anonymous games. (English) Zbl 1322.91005 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). 381-390 (2015). MSC: 91A06 68Q25 91A10 PDFBibTeX XMLCite \textit{X. Chen} 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). 381--390 (2015; Zbl 1322.91005) Full Text: DOI arXiv
Cole, Richard; Gkatzelis, Vasilis Approximating the Nash social welfare with indivisible items. (English) Zbl 1322.91030 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). 371-380 (2015). MSC: 91B15 91B32 90C27 68W25 PDFBibTeX XMLCite \textit{R. Cole} and \textit{V. Gkatzelis}, 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). 371--380 (2015; Zbl 1322.91030) Full Text: DOI
Barman, Siddharth Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory’s theorem. (English) Zbl 1322.91006 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). 361-369 (2015). MSC: 91A10 91A05 68W25 PDFBibTeX XMLCite \textit{S. Barman}, 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). 361--369 (2015; Zbl 1322.91006) Full Text: DOI arXiv
Gowers, Timothy; Viola, Emanuele The communication complexity of interleaved group products. (English) Zbl 1321.94063 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). 351-360 (2015). MSC: 94A60 20P05 PDFBibTeX XMLCite \textit{T. Gowers} and \textit{E. Viola}, 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). 351--360 (2015; Zbl 1321.94063) Full Text: DOI
Braverman, Mark; Weinstein, Omri An interactive information odometer and applications. (English) Zbl 1321.68260 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). 341-350 (2015). MSC: 68P30 68M12 68Q25 91A05 94A15 94A60 PDFBibTeX XMLCite \textit{M. Braverman} and \textit{O. Weinstein}, 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). 341--350 (2015; Zbl 1321.68260) Full Text: DOI
Braverman, Mark; Garg, Ankit Small value parallel repetition for general games. (English) Zbl 1322.91010 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). 335-340 (2015). MSC: 91A20 94A15 PDFBibTeX XMLCite \textit{M. Braverman} and \textit{A. Garg}, 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). 335--340 (2015; Zbl 1322.91010) Full Text: DOI
Bacon, Dave; Flammia, Steven T.; Harrow, Aram W.; Shi, Jonathan Sparse quantum codes from quantum circuits. (English) Zbl 1321.81018 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). 327-334 (2015). MSC: 81P70 PDFBibTeX XMLCite \textit{D. Bacon} 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). 327--334 (2015; Zbl 1321.81018) Full Text: DOI arXiv
Touchette, Dave Quantum information complexity. (English) Zbl 1321.94022 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). 317-326 (2015). MSC: 94A15 68Q12 81P45 PDFBibTeX XMLCite \textit{D. Touchette}, 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). 317--326 (2015; Zbl 1321.94022) Full Text: DOI arXiv
Aaronson, Scott; Ambainis, Andris Forrelation: a problem that optimally separates quantum from classical computing. (English) Zbl 1321.68272 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). 307-316 (2015). MSC: 68Q12 68Q25 68W20 81P68 PDFBibTeX XMLCite \textit{S. Aaronson} and \textit{A. Ambainis}, 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). 307--316 (2015; Zbl 1321.68272) Full Text: DOI
Abbe, Emmanuel; Shpilka, Amir; Wigderson, Avi Reed-Muller codes for random erasures and errors. (English) Zbl 1321.94117 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). 297-306 (2015). MSC: 94B05 68Q17 PDFBibTeX XMLCite \textit{E. Abbe} 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). 297--306 (2015; Zbl 1321.94117) Full Text: DOI arXiv
Chen, Zitan; Jaggi, Sidharth; Langberg, Michael A characterization of the capacity of online (causal) binary channels. (English) Zbl 1321.94121 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). 287-296 (2015). MSC: 94B05 68Q17 PDFBibTeX XMLCite \textit{Z. Chen} 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). 287--296 (2015; Zbl 1321.94121) Full Text: DOI arXiv
Bhowmick, Abhishek; Lovett, Shachar The list decoding radius of Reed-Muller codes over small fields. (English) Zbl 1321.94120 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). 277-285 (2015). MSC: 94B05 94B35 PDFBibTeX XMLCite \textit{A. Bhowmick} and \textit{S. Lovett}, 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). 277--285 (2015; Zbl 1321.94120) Full Text: DOI arXiv
Dinur, Irit; Harsha, Prahladh; Kindler, Guy Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition. (English) Zbl 1321.68305 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). 267-276 (2015). MSC: 68Q25 68Q15 68Q45 PDFBibTeX XMLCite \textit{I. Dinur} 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). 267--276 (2015; Zbl 1321.68305) Full Text: DOI arXiv
Göös, Mika; Lovett, Shachar; Meka, Raghu; Watson, Thomas; Zuckerman, David Rectangles are nonnegative juntas. (English) Zbl 1321.68313 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). 257-266 (2015). MSC: 68Q25 68Q15 PDFBibTeX XMLCite \textit{M. Göös} 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). 257--266 (2015; Zbl 1321.68313) Full Text: DOI Link
Kothari, Pravesh K.; Meka, Raghu Almost optimal pseudorandom generators for spherical caps (extended abstract). (English) Zbl 1321.65008 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). 247-256 (2015). MSC: 65C10 68Q25 PDFBibTeX XMLCite \textit{P. K. Kothari} and \textit{R. Meka}, 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). 247--256 (2015; Zbl 1321.65008) Full Text: DOI
Allen-Zhu, Zeyuan; Liao, Zhenyu; Orecchia, Lorenzo Spectral sparsification and regret minimization beyond matrix multiplicative updates. (English) Zbl 1321.68294 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). 237-245 (2015). MSC: 68Q25 05C50 65F50 68W20 PDFBibTeX XMLCite \textit{Z. Allen-Zhu} 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). 237--245 (2015; Zbl 1321.68294) Full Text: DOI arXiv
Allen-Zhu, Zeyuan; Orecchia, Lorenzo Nearly-linear time positive LP solver with faster convergence rate. (English) Zbl 1321.90078 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). 229-236 (2015). MSC: 90C05 68W25 PDFBibTeX XMLCite \textit{Z. Allen-Zhu} and \textit{L. Orecchia}, 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). 229--236 (2015; Zbl 1321.90078) Full Text: DOI arXiv
Chawla, Shuchi; Makarychev, Konstantin; Schramm, Tselil; Yaroslavtsev, Grigory Near optimal LP rounding algorithm for correlation clustering on complete and complete \(k\)-partite graphs. (English) Zbl 1321.68495 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). 219-228 (2015). MSC: 68W25 05C22 05C85 90C05 PDFBibTeX XMLCite \textit{S. Chawla} 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). 219--228 (2015; Zbl 1321.68495) Full Text: DOI arXiv
Hansen, Thomas Dueholm; Zwick, Uri An improved version of the random-facet pivoting rule for the simplex algorithm. (English) Zbl 1321.90080 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). 209-218 (2015). MSC: 90C05 68Q25 68W20 PDFBibTeX XMLCite \textit{T. D. Hansen} and \textit{U. Zwick}, 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). 209--218 (2015; Zbl 1321.90080) Full Text: DOI
Fearnley, John; Savani, Rahul The complexity of the simplex method. (English) Zbl 1321.90079 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). 201-208 (2015). MSC: 90C05 90C40 68Q25 PDFBibTeX XMLCite \textit{J. Fearnley} and \textit{R. Savani}, 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). 201--208 (2015; Zbl 1321.90079) Full Text: DOI arXiv
Bansal, Nikhil; Gupta, Anupam; Guruganesh, Guru On the Lovász theta function for independent sets in sparse graphs. (English) Zbl 1321.05176 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). 193-200 (2015). MSC: 05C69 05C55 05C85 68Q25 68W25 90C22 PDFBibTeX XMLCite \textit{N. Bansal} 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). 193--200 (2015; Zbl 1321.05176) Full Text: DOI arXiv
Cohen, Michael B.; Peng, Richard \(\ell_p\) row sampling by Lewis weights. (English) Zbl 1321.65064 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). 183-192 (2015). MSC: 65F30 68Q17 PDFBibTeX XMLCite \textit{M. B. Cohen} and \textit{R. Peng}, 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). 183--192 (2015; Zbl 1321.65064) Full Text: DOI arXiv
Bhattacharya, Sayan; Henzinger, Monika; Nanongkai, Danupon; Tsourakakis, Charalampos Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. (English) Zbl 1321.05253 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). 173-182 (2015). MSC: 05C85 05C42 68Q17 68Q25 68R10 68W25 PDFBibTeX XMLCite \textit{S. Bhattacharya} 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). 173--182 (2015; Zbl 1321.05253) Full Text: DOI arXiv
Cohen, Michael B.; Elder, Sam; Musco, Cameron; Musco, Christopher; Persu, Madalina Dimensionality reduction for \(k\)-means clustering and low rank approximation. (English) Zbl 1321.68398 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). 163-172 (2015). MSC: 68T05 62H25 62H30 PDFBibTeX XMLCite \textit{M. B. Cohen} 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). 163--172 (2015; Zbl 1321.68398) Full Text: DOI arXiv
Mirrokni, Vahab; Zadimoghaddam, Morteza Randomized composable core-sets for distributed submodular maximization. (English) Zbl 1321.68361 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). 153-162 (2015). MSC: 68Q85 68Q17 68W15 68W20 PDFBibTeX XMLCite \textit{V. Mirrokni} and \textit{M. Zadimoghaddam}, 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). 153--162 (2015; Zbl 1321.68361) Full Text: DOI arXiv
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
Lovett, Shachar; Zhang, Jiapeng Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions. (English) Zbl 1321.68317 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). 137-142 (2015). MSC: 68Q25 68T05 PDFBibTeX XMLCite \textit{S. Lovett} and \textit{J. Zhang}, 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). 137--142 (2015; Zbl 1321.68317) Full Text: DOI
Bassily, Raef; Smith, Adam Local, private, efficient protocols for succinct histograms. (English) Zbl 1321.94037 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). 127-135 (2015). MSC: 94A60 68Q17 PDFBibTeX XMLCite \textit{R. Bassily} and \textit{A. Smith}, 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). 127--135 (2015; Zbl 1321.94037) Full Text: DOI arXiv
Dwork, Cynthia; Feldman, Vitaly; Hardt, Moritz; Pitassi, Toniann; Reingold, Omer; Roth, Aaron Leon Preserving statistical validity in adaptive data analysis (extended abstract). (English) Zbl 1321.68401 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). 117-126 (2015). MSC: 68T05 94A60 PDFBibTeX XMLCite \textit{C. Dwork} 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). 117--126 (2015; Zbl 1321.68401) Full Text: DOI arXiv
Braun, Gábor; Pokutta, Sebastian; Zink, Daniel Inapproximability of combinatorial problems via small LPs and SDPs. (English) Zbl 1321.90098 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). 107-116 (2015). MSC: 90C22 90C27 68Q25 PDFBibTeX XMLCite \textit{G. Braun} 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). 107--116 (2015; Zbl 1321.90098) Full Text: DOI
Barak, Boaz; Chan, Siu On; Kothari, Pravesh K. Sum of squares lower bounds from pairwise independence (extended abstract). (English) Zbl 1321.68295 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). 97-106 (2015). MSC: 68Q25 68Q17 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). 97--106 (2015; Zbl 1321.68295) Full Text: DOI arXiv
Meka, Raghu; Potechin, Aaron; Wigderson, Avi Sum-of-squares lower bounds for planted clique (extended abstract). (English) Zbl 1321.05241 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). 87-96 (2015). MSC: 05C80 05C69 15B52 68Q17 68Q25 PDFBibTeX XMLCite \textit{R. Meka} 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). 87--96 (2015; Zbl 1321.05241) Full Text: DOI arXiv
Feldman, Vitaly; Perkins, Will; Vempala, Santosh On the complexity of random satisfiability problems with planted solutions (extended abstract). (English) Zbl 1321.68280 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). 77-86 (2015). MSC: 68Q17 68Q25 PDFBibTeX XMLCite \textit{V. Feldman} 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). 77--86 (2015; Zbl 1321.68280) Full Text: DOI arXiv
Mossel, Elchanan; Neeman, Joe; Sly, Allan Consistency thresholds for the planted bisection model. (English) Zbl 1321.05242 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). 69-75 (2015). MSC: 05C80 05C85 68Q25 PDFBibTeX XMLCite \textit{E. Mossel} 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). 69--75 (2015; Zbl 1321.05242) Full Text: DOI arXiv
Ding, Jian; Sly, Allan; Sun, Nike Proof of the satisfiability conjecture for large \(k\). (English) Zbl 1321.68304 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). 59-68 (2015). MSC: 68Q25 PDFBibTeX XMLCite \textit{J. Ding} 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). 59--68 (2015; Zbl 1321.68304) Full Text: DOI arXiv
Backurs, Arturs; Indyk, Piotr Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). (English) Zbl 1321.68548 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). 51-58 (2015). MSC: 68W32 68Q17 68Q25 PDFBibTeX XMLCite \textit{A. Backurs} and \textit{P. Indyk}, 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). 51--58 (2015; Zbl 1321.68548) Full Text: DOI arXiv
Abboud, Amir; Vassilevska Williams, Virginia; Yu, Huacheng Matching triangles and basing hardness on an extremely popular conjecture. (English) Zbl 1321.68291 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). 41-50 (2015). MSC: 68Q25 05C21 68Q17 PDFBibTeX XMLCite \textit{A. Abboud} 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). 41--50 (2015; Zbl 1321.68291) Full Text: DOI
Chan, Timothy M.; Lewenstein, Moshe Clustered integer 3SUM via additive combinatorics. (English) Zbl 1321.68299 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). 31-40 (2015). MSC: 68Q25 68Q17 68R05 PDFBibTeX XMLCite \textit{T. M. Chan} and \textit{M. Lewenstein}, 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). 31--40 (2015; Zbl 1321.68299) Full Text: DOI arXiv