default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID47th 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
- Shiri Chechik:
Approximate Distance Oracles with Improved Bounds. 1-10 - 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 - Timothy M. Chan, Moshe Lewenstein:
Clustered Integer 3SUM via Additive Combinatorics. 31-40 - 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
- Jian Ding, Allan Sly, Nike Sun:
Proof of the Satisfiability Conjecture for Large k. 59-68 - Elchanan Mossel, Joe Neeman, Allan Sly:
Consistency Thresholds for the Planted Bisection Model. 69-75 - Vitaly Feldman, Will Perkins, Santosh S. Vempala:
On the Complexity of Random Satisfiability Problems with Planted Solutions. 77-86 - Raghu Meka, Aaron Potechin, Avi Wigderson:
Sum-of-squares Lower Bounds for Planted Clique. 87-96 - 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 - Raef Bassily, Adam D. Smith:
Local, Private, Efficient Protocols for Succinct Histograms. 127-135 - 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 - Michael B. Cohen, Richard Peng:
Lp Row Sampling by Lewis Weights. 183-192
Session 3A
- Nikhil Bansal, Anupam Gupta, Guru Guruganesh:
On the Lovász Theta function for Independent Sets in Sparse Graphs. 193-200 - John Fearnley, Rahul Savani:
The Complexity of the Simplex Method. 201-208 - 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 Touchette:
Quantum Information Complexity. 317-326 - Dave Bacon, Steven T. Flammia, Aram W. Harrow, Jonathan Shi:
Sparse Quantum Codes from Quantum Circuits. 327-334 - Mark Braverman, Ankit Garg:
Small Value Parallel Repetition for General Games. 335-340 - Mark Braverman, Omri Weinstein:
An Interactive Information Odometer and Applications. 341-350 - Timothy Gowers, Emanuele Viola:
The communication complexity of interleaved group products. 351-360
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 - Euiwoong Lee:
Hardness of Graph Pricing Through Generalized Max-Dicut. 391-399 - Amit Daniely, Michael Schapira, Gal Shahaf:
Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension. 401-408 - Aviad Rubinstein:
Inapproximability of Nash Equilibrium. 409-418
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 - Michael Elkin, Arnold Filtser, Ofer Neiman:
Prioritized Metric Structures and Embedding. 489-498 - 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 - Ryan O'Donnell, John Wright:
Quantum Spectrum Testing. 529-538
Session 6B
- Benjamin Cousins, Santosh S. Vempala:
Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm. 539-548 - Jingcheng Liu, Pinyan Lu:
FPTAS for #BIS with Degree Bounds on One Side. 549-556
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 - Zeev Dvir, Sivakanth Gopi:
2-Server PIR with Sub-Polynomial Communication. 577-584
Session 8A
- Andris Ambainis, Yuval Filmus, François Le Gall:
Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method. 585-593 - Joël Alwen, Vladimir Serbinenko:
High Parallel Complexity Graphs and Memory-Hard Functions. 595-603 - 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 - Magnús M. Halldórsson, Tigran Tonoyan:
How Well Can Graphs Represent Wireless Interference? 635-644
Session 8B
- Julia Chuzhoy:
Excluded Grid Theorem: Improved and Simplified. 645-654 - Ken-ichi Kawarabayashi, Stephan Kreutzer:
The Directed Grid Theorem. 655-664 - 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 - Martin Grohe, Pascal Schweitzer:
Computing with Tangles. 683-692 - Xiaorui Sun, John Wilmes:
Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract. 693-702
Session 9A
- Artur Czumaj:
Random Permutations using Switching Networks. 703-712 - Anand Louis:
Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms. 713-722 - Artur Czumaj, Pan Peng, Christian Sohler:
Testing Cluster Structure of Graphs. 723-732 - 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 - Moritz Hardt, Eric Price:
Tight Bounds for Learning a Mixture of Two Gaussians. 753-760 - Rong Ge, Qingqing Huang, Sham M. Kakade:
Learning Mixtures of Gaussians in High Dimensions. 761-770 - Guy Bresler:
Efficiently Learning Ising Models on Arbitrary Graphs. 771-782
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 - Nikhil Bansal, Janardhan Kulkarni:
Minimizing Flow-Time on Unrelated Machines. 851-860 - Aleksandar Nikolov:
Randomized Rounding for the Largest Simplex Problem. 861-870 - Anupam Gupta, Amit Kumar:
Greedy Algorithms for Steiner Forest. 871-878 - 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-02 20:54 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
