STOC '15- Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing
Full Citation in the ACM Digital Library
SESSION: Session 1A
Approximate Distance Oracles with Improved Bounds
Shiri Chechik
The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree
Jakub Łącki
Jakub Oćwieja
Marcin Pilipczuk
Piotr Sankowski
Anna Zych
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Monika Henzinger
Sebastian Krinninger
Danupon Nanongkai
Thatchaphol Saranurak
Clustered Integer 3SUM via Additive Combinatorics
Timothy M. Chan
Moshe Lewenstein
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
Amir Abboud
Virginia Vassilevska Williams
Huacheng Yu
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
Arturs Backurs
Piotr Indyk
SESSION: Session 1B
Proof of the Satisfiability Conjecture for Large k
Jian Ding
Allan Sly
Nike Sun
Consistency Thresholds for the Planted Bisection Model
Elchanan Mossel
Joe Neeman
Allan Sly
On the Complexity of Random Satisfiability Problems with Planted Solutions
Vitaly Feldman
Will Perkins
Santosh Vempala
Sum-of-squares Lower Bounds for Planted Clique
Raghu Meka
Aaron Potechin
Avi Wigderson
Sum of Squares Lower Bounds from Pairwise Independence
Boaz Barak
Siu On Chan
Pravesh K. Kothari
Inapproximability of Combinatorial Problems via Small LPs and SDPs
Gábor Braun
Sebastian Pokutta
Daniel Zink
SESSION: Session 2A
Preserving Statistical Validity in Adaptive Data Analysis
Cynthia Dwork
Vitaly Feldman
Moritz Hardt
Toniann Pitassi
Omer Reingold
Aaron Leon Roth
Local, Private, Efficient Protocols for Succinct Histograms
Raef Bassily
Adam Smith
Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions
Shachar Lovett
Jiapeng Zhang
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Boaz Barak
Jonathan A. Kelner
David Steurer
SESSION: Session 2B
Randomized Composable Core-sets for Distributed Submodular Maximization
Vahab Mirrokni
Morteza Zadimoghaddam
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
Michael B. Cohen
Sam Elder
Cameron Musco
Christopher Musco
Madalina Persu
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
Sayan Bhattacharya
Monika Henzinger
Danupon Nanongkai
Charalampos Tsourakakis
L
p
Row Sampling by Lewis Weights
Michael B. Cohen
Richard Peng
SESSION: Session 3A
On the Lovász Theta function for Independent Sets in Sparse Graphs
Nikhil Bansal
Anupam Gupta
Guru Guruganesh
The Complexity of the Simplex Method
John Fearnley
Rahul Savani
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
Thomas Dueholm Hansen
Uri Zwick
Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
Shuchi Chawla
Konstantin Makarychev
Tselil Schramm
Grigory Yaroslavtsev
Nearly-Linear Time Positive LP Solver with Faster Convergence Rate
Zeyuan Allen-Zhu
Lorenzo Orecchia
Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
Zeyuan Allen-Zhu
Zhenyu Liao
Lorenzo Orecchia
SESSION: Session 3B
Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract
Pravesh K. Kothari
Raghu Meka
Rectangles Are Nonnegative Juntas
Mika Göös
Shachar Lovett
Raghu Meka
Thomas Watson
David Zuckerman
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition
Irit Dinur
Prahladh Harsha
Guy Kindler
The List Decoding Radius of Reed-Muller Codes over Small Fields
Abhishek Bhowmick
Shachar Lovett
A Characterization of the Capacity of Online (Causal) Binary Channels
Zitan Chen
Sidharth Jaggi
Michael Langberg
Reed-Muller Codes for Random Erasures and Errors
Emmanuel Abbe
Amir Shpilka
Avi Wigderson
SESSION: Session 4A
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
Scott Aaronson
Andris Ambainis
Quantum Information Complexity
Dave Touchette
Sparse Quantum Codes from Quantum Circuits
Dave Bacon
Steven T. Flammia
Aram W. Harrow
Jonathan Shi
Small Value Parallel Repetition for General Games
Mark Braverman
Ankit Garg
An Interactive Information Odometer and Applications
Mark Braverman
Omri Weinstein
The Communication Complexity of Interleaved Group Products
Timothy Gowers
Emanuele Viola
SESSION: Session 4B
Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem
Siddharth Barman
Approximating the Nash Social Welfare with Indivisible Items
Richard Cole
Vasilis Gkatzelis
On the Complexity of Nash Equilibria in Anonymous Games
Xi Chen
David Durfee
Anthi Orfanou
Hardness of Graph Pricing Through Generalized Max-Dicut
Euiwoong Lee
Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
Amit Daniely
Michael Schapira
Gal Shahaf
Inapproximability of Nash Equilibrium
Aviad Rubinstein
SESSION: Session 5A
Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
Venkata Koppula
Allison Bishop Lewko
Brent Waters
Succinct Garbling and Indistinguishability Obfuscation for RAM Programs
Ran Canetti
Justin Holmgren
Abhishek Jain
Vinod Vaikuntanathan
Succinct Randomized Encodings and their Applications
Nir Bitansky
Sanjam Garg
Huijia Lin
Rafael Pass
Sidharth Telang
Garbled RAM From One-Way Functions
Sanjam Garg
Steve Lu
Rafail Ostrovsky
Alessandra Scafuro
Non-malleable Reductions and Applications
Divesh Aggarwal
Yevgeniy Dodis
Tomasz Kazana
Maciej Obremski
Leveled Fully Homomorphic Signatures from Standard Lattices
Sergey Gorbunov
Vinod Vaikuntanathan
Daniel Wichs
SESSION: Session 5B
Sketching and Embedding are Equivalent for Norms
Alexandr Andoni
Robert Krauthgamer
Ilya Razenshteyn
Prioritized Metric Structures and Embedding
Michael Elkin
Arnold Filtser
Ofer Neiman
Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space
Jean Bourgain
Sjoerd Dirksen
Jelani Nelson
A Directed Isoperimetric Inequality with Application to Bregman Near Neighbor Lower Bounds
Amirali Abdullah
Suresh Venkatasubramanian
SESSION: Session 6A
Boolean Function Monotonicity Testing Requires (Almost) n
1/2
Non-adaptive Queries
Xi Chen
Anindya De
Rocco A. Servedio
Li-Yang Tan
Quantum Spectrum Testing
Ryan O'Donnell
John Wright
SESSION: Session 6B
Bypassing KLS: Gaussian Cooling and an O*(n
3
) Volume Algorithm
Benjamin Cousins
Santosh Vempala
FPTAS for #BIS with Degree Bounds on One Side
Jingcheng Liu
Pinyan Lu
SESSION: Session 7
Exponential Separation of Information and Communication for Boolean Functions
Anat Ganor
Gillat Kol
Ran Raz
Lower Bounds on the Size of Semidefinite Programming Relaxations
James R. Lee
Prasad Raghavendra
David Steurer
2-Server PIR with Sub-Polynomial Communication
Zeev Dvir
Sivakanth Gopi
SESSION: Session 8A
Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method
Andris Ambainis
Yuval Filmus
François Le Gall
High Parallel Complexity Graphs and Memory-Hard Functions
Joël Alwen
Vladimir Serbinenko
Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity
Ittai Abraham
Danny Dolev
Test-and-Set in Optimal Space
George Giakkoupis
Maryam Helmi
Lisa Higham
Philipp Woelfel
Adjacency Labeling Schemes and Induced-Universal Graphs
Stephen Alstrup
Haim Kaplan
Mikkel Thorup
Uri Zwick
How Well Can Graphs Represent Wireless Interference?
Magnus M. Halldorsson
Tigran Tonoyan
SESSION: Session 8B
Excluded Grid Theorem: Improved and Simplified
Julia Chuzhoy
The Directed Grid Theorem
Ken-ichi Kawarabayashi
Stephan Kreutzer
Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
Ken-ichi Kawarabayashi
Mikkel Thorup
Beyond the Euler Characteristic: Approximating the Genus of General Graphs
Ken-ichi Kawarabayashi
Anastasios Sidiropoulos
Computing with Tangles
Martin Grohe
Pascal Schweitzer
Faster Canonical Forms for Primitive Coherent Configurations
Xiaorui Sun
John Wilmes
SESSION: Session 9A
Random Permutations using Switching Networks
Artur Czumaj
Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
Anand Louis
Testing Cluster Structure of Graphs
Artur Czumaj
Pan Peng
Christian Sohler
Solving the Shortest Vector Problem in 2
n
Time Using Discrete Gaussian Sampling
Divesh Aggarwal
Daniel Dadush
Oded Regev
Noah Stephens-Davidowitz
SESSION: Session 9B
Learning Arbitrary Statistical Mixtures of Discrete Distributions
Jian Li
Yuval Rabani
Leonard J. Schulman
Chaitanya Swamy
Tight Bounds for Learning a Mixture of Two Gaussians
Moritz Hardt
Eric Price
Learning Mixtures of Gaussians in High Dimensions
Rong Ge
Qingqing Huang
Sham M. Kakade
Efficiently Learning Ising Models on Arbitrary Graphs
Guy Bresler
SESSION: Session 10A
Approximate k-flat Nearest Neighbor Search
Wolfgang Mulzer
Huy L. Nguyên
Paul Seiferth
Yannik Stein
Optimal Data-Dependent Hashing for Approximate Near Neighbors
Alexandr Andoni
Ilya Razenshteyn
Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms
Kasper Green Larsen
Jelani Nelson
Huy L. Nguyên
From Independence to Expansion and Back Again
Tobias Christiani
Rasmus Pagh
Mikkel Thorup
Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
Ankur Moitra
Analysis of a Classical Matrix Preconditioning Algorithm
Leonard J. Schulman
Alistair Sinclair
SESSION: Session 10B
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
Kyle Fox
Philip N. Klein
Shay Mozes
Minimizing Flow-Time on Unrelated Machines
Nikhil Bansal
Janardhan Kulkarni
Randomized Rounding for the Largest Simplex Problem
Aleksandar Nikolov
Greedy Algorithms for Steiner Forest
Anupam Gupta
Amit Kumar
Secretary Problems with Non-Uniform Arrival Order
Thomas Kesselheim
Robert Kleinberg
Rad Niazadeh
Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
Nitish Korula
Vahab Mirrokni
Morteza Zadimoghaddam