Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic Scholar47. STOC 2015: Portland, OR, USA
Rocco A. Servedio, Ronitt Rubinfeld:
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015. ACM 2015, ISBN 978-1-4503-3536-2
Session 1A
- Jakub Lacki, Jakub Ocwieja, Marcin Pilipczuk, Piotr Sankowski, Anna Zych:
The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree. 11-20 - Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak:
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. 21-30 - Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu:
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. 41-50 - Arturs Backurs, Piotr Indyk:
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). 51-58
Session 1B
- Elchanan Mossel, Joe Neeman, Allan Sly:
Consistency Thresholds for the Planted Bisection Model. 69-75 - Vitaly Feldman, Will Perkins, Santosh Vempala:
On the Complexity of Random Satisfiability Problems with Planted Solutions. 77-86 - Boaz Barak, Siu On Chan, Pravesh K. Kothari:
Sum of Squares Lower Bounds from Pairwise Independence. 97-106 - Gábor Braun, Sebastian Pokutta, Daniel Zink:
Inapproximability of Combinatorial Problems via Small LPs and SDPs. 107-116
Session 2A
- Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Leon Roth:
Preserving Statistical Validity in Adaptive Data Analysis. 117-126 - Shachar Lovett, Jiapeng Zhang:
Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions. 137-142 - Boaz Barak, Jonathan A. Kelner, David Steurer:
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. 143-151
Session 2B
- Vahab S. Mirrokni, Morteza Zadimoghaddam:
Randomized Composable Core-sets for Distributed Submodular Maximization. 153-162 - Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu:
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation. 163-172 - Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Charalampos E. Tsourakakis:
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. 173-182
Session 3A
- Nikhil Bansal, Anupam Gupta, Guru Guruganesh:
On the Lovász Theta function for Independent Sets in Sparse Graphs. 193-200 - Thomas Dueholm Hansen, Uri Zwick:
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm. 209-218 - Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev:
Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs. 219-228 - Zeyuan Allen Zhu, Lorenzo Orecchia:
Nearly-Linear Time Positive LP Solver with Faster Convergence Rate. 229-236 - Zeyuan Allen Zhu, Zhenyu Liao, Lorenzo Orecchia:
Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates. 237-245
Session 3B
- Pravesh K. Kothari, Raghu Meka:
Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract. 247-256 - Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman:
Rectangles Are Nonnegative Juntas. 257-266 - Irit Dinur, Prahladh Harsha, Guy Kindler:
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition. 267-276 - Abhishek Bhowmick, Shachar Lovett:
The List Decoding Radius of Reed-Muller Codes over Small Fields. 277-285 - Zitan Chen, Sidharth Jaggi, Michael Langberg:
A Characterization of the Capacity of Online (causal) Binary Channels. 287-296 - Emmanuel Abbe, Amir Shpilka, Avi Wigderson:
Reed-Muller Codes for Random Erasures and Errors. 297-306
Session 4A
- Scott Aaronson, Andris Ambainis:
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. 307-316 - Dave Bacon, Steven T. Flammia, Aram Wettroth Harrow, Jonathan Shi:
Sparse Quantum Codes from Quantum Circuits. 327-334
Session 4B
- Siddharth Barman:
Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem. 361-369 - Richard Cole, Vasilis Gkatzelis:
Approximating the Nash Social Welfare with Indivisible Items. 371-380 - Xi Chen, David Durfee, Anthi Orfanou:
On the Complexity of Nash Equilibria in Anonymous Games. 381-390 - Amit Daniely, Michael Schapira, Gal Shahaf:
Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension. 401-408
Session 5A
- Venkata Koppula, Allison Bishop Lewko, Brent Waters:
Indistinguishability Obfuscation for Turing Machines with Unbounded Memory. 419-428 - Ran Canetti, Justin Holmgren, Abhishek Jain, Vinod Vaikuntanathan:
Succinct Garbling and Indistinguishability Obfuscation for RAM Programs. 429-437 - Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, Sidharth Telang:
Succinct Randomized Encodings and their Applications. 439-448 - Sanjam Garg, Steve Lu, Rafail Ostrovsky, Alessandra Scafuro:
Garbled RAM From One-Way Functions. 449-458 - Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, Maciej Obremski:
Non-malleable Reductions and Applications. 459-468 - Sergey Gorbunov, Vinod Vaikuntanathan, Daniel Wichs:
Leveled Fully Homomorphic Signatures from Standard Lattices. 469-477
Session 5B
- Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn:
Sketching and Embedding are Equivalent for Norms. 479-488 - Jean Bourgain, Sjoerd Dirksen, Jelani Nelson:
Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space. 499-508 - Amirali Abdullah, Suresh Venkatasubramanian:
A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds. 509-518
Session 6A
- Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan:
Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries. 519-528
Session 6B
- Benjamin Cousins, Santosh Vempala:
Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm. 539-548
Session 7
- Anat Ganor, Gillat Kol, Ran Raz:
Exponential Separation of Information and Communication for Boolean Functions. 557-566 - James R. Lee, Prasad Raghavendra, David Steurer:
Lower Bounds on the Size of Semidefinite Programming Relaxations. 567-576
Session 8A
- Andris Ambainis, Yuval Filmus, François Le Gall:
Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method. 585-593 - Ittai Abraham, Danny Dolev:
Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity. 605-614 - George Giakkoupis, Maryam Helmi, Lisa Higham, Philipp Woelfel:
Test-and-Set in Optimal Space. 615-623 - Stephen Alstrup, Haim Kaplan, Mikkel Thorup, Uri Zwick:
Adjacency Labeling Schemes and Induced-Universal Graphs. 625-634
Session 8B
- Ken-ichi Kawarabayashi, Mikkel Thorup:
Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time. 665-674 - Ken-ichi Kawarabayashi, Anastasios Sidiropoulos:
Beyond the Euler Characteristic: Approximating the Genus of General Graphs. 675-682 - Xiaorui Sun, John Wilmes:
Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract. 693-702
Session 9A
- Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz:
Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian Sampling: Extended Abstract. 733-742
Session 9B
- Jian Li, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy:
Learning Arbitrary Statistical Mixtures of Discrete Distributions. 743-752
Session 10A
- Wolfgang Mulzer, Huy L. Nguyên, Paul Seiferth, Yannik Stein:
Approximate k-flat Nearest Neighbor Search. 783-792 - Alexandr Andoni, Ilya P. Razenshteyn:
Optimal Data-Dependent Hashing for Approximate Near Neighbors. 793-801 - Kasper Green Larsen, Jelani Nelson, Huy L. Nguyên:
Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms. 803-812 - Tobias Christiani, Rasmus Pagh, Mikkel Thorup:
From Independence to Expansion and Back Again. 813-820 - Ankur Moitra:
Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices. 821-830 - Leonard J. Schulman, Alistair Sinclair:
Analysis of a Classical Matrix Preconditioning Algorithm. 831-840
Session 10B
- Kyle Fox, Philip N. Klein, Shay Mozes:
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection. 841-850 - Thomas Kesselheim, Robert D. Kleinberg, Rad Niazadeh:
Secretary Problems with Non-Uniform Arrival Order. 879-888 - Nitish Korula, Vahab S. Mirrokni, Morteza Zadimoghaddam:
Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order. 889-898
maintained by 
at 
at 
data released under the ODC-BY 1.0 license; see also our legal information page
last updated on 2018-04-19 21:38 CEST by the dblp team