ACM Symposium on Theory of Computing, STOC 2015


The information below was collected semi-automatically. The authors have not yet been given the opportunity to verify the data.
[?] We ask all authors to verify the information we have about their papers, in particular the location of any supporting artifacts. We send out emails to authors asking them to update or verify this information incrementally, one conference at a time. For conferences where these emails have yet to be sent out we present the information in gray text.
Title/Authors Title Research Artifacts
[?] A research artifact is any by-product of a research project that is not directly included in the published research paper. In Computer Science research this is often source code and data sets, but it could also be media, documentation, inputs to proof assistants, shell-scripts to run experiments, etc.
Details

Inapproximability of Nash Equilibrium

Aviad Rubinstein

Inapproximability of Nash Equilibrium

Details
Discussion Comments: 0
Verification: Author has not verified information

Preserving Statistical Validity in Adaptive Data Analysis

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Leon Roth

Preserving Statistical Validity in Adaptive Data Analysis

Details
Discussion Comments: 0
Verification: Authors have not verified information

FPTAS for #BIS with Degree Bounds on One Side

Jingcheng Liu, Pinyan Lu

FPTAS for #BIS with Degree Bounds on One Side

Details
Discussion Comments: 0
Verification: Authors have not verified information

Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract

Xiaorui Sun, John Wilmes

Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract

Details
Discussion Comments: 0
Verification: Authors have not verified information

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture

Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture

Details
Discussion Comments: 0
Verification: Authors have not verified information

Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension

Amit Daniely, Michael Schapira, Gal Shahaf

Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension

Details
Discussion Comments: 0
Verification: Authors have not verified information

Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates

Zeyuan Allen Zhu, Zhenyu Liao, Lorenzo Orecchia

Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates

Details
Discussion Comments: 0
Verification: Authors have not verified information

Indistinguishability Obfuscation for Turing Machines with Unbounded Memory

Venkata Koppula, Allison Bishop Lewko, Brent Waters

Indistinguishability Obfuscation for Turing Machines with Unbounded Memory

Details
Discussion Comments: 0
Verification: Authors have not verified information

Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs

Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev

Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Hardness of Graph Pricing Through Generalized Max-Dicut

Euiwoong Lee

Hardness of Graph Pricing Through Generalized Max-Dicut

Details
Discussion Comments: 0
Verification: Author has not verified information

Consistency Thresholds for the Planted Bisection Model

Elchanan Mossel, Joe Neeman, Allan Sly

Consistency Thresholds for the Planted Bisection Model

Details
Discussion Comments: 0
Verification: Authors have not verified information

Beyond the Euler Characteristic: Approximating the Genus of General Graphs

Ken-ichi Kawarabayashi, Anastasios Sidiropoulos

Beyond the Euler Characteristic: Approximating the Genus of General Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds

Amirali Abdullah, Suresh Venkatasubramanian

A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds

Details
Discussion Comments: 0
Verification: Authors have not verified information

Tight Bounds for Learning a Mixture of Two Gaussians

Moritz Hardt, Eric Price

Tight Bounds for Learning a Mixture of Two Gaussians

Details
Discussion Comments: 0
Verification: Authors have not verified information

Leveled Fully Homomorphic Signatures from Standard Lattices

Sergey Gorbunov, Vinod Vaikuntanathan, Daniel Wichs

Leveled Fully Homomorphic Signatures from Standard Lattices

Details
Discussion Comments: 0
Verification: Authors have not verified information

Exponential Separation of Information and Communication for Boolean Functions

Anat Ganor, Gillat Kol, Ran Raz

Exponential Separation of Information and Communication for Boolean Functions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sum of Squares Lower Bounds from Pairwise Independence

Boaz Barak, Siu On Chan, Pravesh K. Kothari

Sum of Squares Lower Bounds from Pairwise Independence

Details
Discussion Comments: 0
Verification: Authors have not verified information

Local, Private, Efficient Protocols for Succinct Histograms

Raef Bassily, Adam D. Smith

Local, Private, Efficient Protocols for Succinct Histograms

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Directed Grid Theorem

Ken-ichi Kawarabayashi, Stephan Kreutzer

The Directed Grid Theorem

Details
Discussion Comments: 0
Verification: Authors have not verified information

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method

Boaz Barak, Jonathan A. Kelner, David Steurer

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method

Details
Discussion Comments: 0
Verification: Authors have not verified information

Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices

Ankur Moitra

Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices

Details
Discussion Comments: 0
Verification: Author has not verified information

Quantum Information Complexity

Dave Touchette

Quantum Information Complexity

Details
Discussion Comments: 0
Verification: Author has not verified information

Learning Arbitrary Statistical Mixtures of Discrete Distributions

Jian Li, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy

Learning Arbitrary Statistical Mixtures of Discrete Distributions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Lower Bounds on the Size of Semidefinite Programming Relaxations

James R. Lee, Prasad Raghavendra, David Steurer

Lower Bounds on the Size of Semidefinite Programming Relaxations

Details
Discussion Comments: 0
Verification: Authors have not verified information

Lp Row Sampling by Lewis Weights

Michael B. Cohen, Richard Peng

Lp Row Sampling by Lewis Weights

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Complexity of Random Satisfiability Problems with Planted Solutions

Vitaly Feldman, Will Perkins, Santosh Vempala

On the Complexity of Random Satisfiability Problems with Planted Solutions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams

Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Charalampos E. Tsourakakis

Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sum-of-squares Lower Bounds for Planted Clique

Raghu Meka, Aaron Potechin, Avi Wigderson

Sum-of-squares Lower Bounds for Planted Clique

Details
Discussion Comments: 0
Verification: Authors have not verified information

Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract

Pravesh K. Kothari, Raghu Meka

Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sketching and Embedding are Equivalent for Norms

Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn

Sketching and Embedding are Equivalent for Norms

Details
Discussion Comments: 0
Verification: Authors have not verified information

Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

Scott Aaronson, Andris Ambainis

Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

Details
Discussion Comments: 0
Verification: Authors have not verified information

Greedy Algorithms for Steiner Forest

Anupam Gupta, Amit Kumar

Greedy Algorithms for Steiner Forest

Details
Discussion Comments: 0
Verification: Authors have not verified information

Computing with Tangles

Martin Grohe, Pascal Schweitzer

Computing with Tangles

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree

Jakub Lacki, Jakub Ocwieja, Marcin Pilipczuk, Piotr Sankowski, Anna Zych

The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree

Details
Discussion Comments: 0
Verification: Authors have not verified information

Non-malleable Reductions and Applications

Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, Maciej Obremski

Non-malleable Reductions and Applications

Details
Discussion Comments: 0
Verification: Authors have not verified information

Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm

Benjamin Cousins, Santosh Vempala

Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm

Details
Discussion Comments: 0
Verification: Authors have not verified information

Randomized Rounding for the Largest Simplex Problem

Aleksandar Nikolov

Randomized Rounding for the Largest Simplex Problem

Details
Discussion Comments: 0
Verification: Author has not verified information

Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms

Kasper Green Larsen, Jelani Nelson, Huy L. Nguyên

Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximate k-flat Nearest Neighbor Search

Wolfgang Mulzer, Huy L. Nguyên, Paul Seiferth, Yannik Stein

Approximate k-flat Nearest Neighbor Search

Details
Discussion Comments: 0
Verification: Authors have not verified information

Adjacency Labeling Schemes and Induced-Universal Graphs

Stephen Alstrup, Haim Kaplan, Mikkel Thorup, Uri Zwick

Adjacency Labeling Schemes and Induced-Universal Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

The communication complexity of interleaved group products

Timothy Gowers, Emanuele Viola

The communication complexity of interleaved group products

Details
Discussion Comments: 0
Verification: Authors have not verified information

Succinct Randomized Encodings and their Applications

Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, Sidharth Telang

Succinct Randomized Encodings and their Applications

Details
Discussion Comments: 0
Verification: Authors have not verified information

Prioritized Metric Structures and Embedding

Michael Elkin, Arnold Filtser, Ofer Neiman

Prioritized Metric Structures and Embedding

Details
Discussion Comments: 0
Verification: Authors have not verified information

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

Details
Discussion Comments: 0
Verification: Authors have not verified information

Optimal Data-Dependent Hashing for Approximate Near Neighbors

Alexandr Andoni, Ilya P. Razenshteyn

Optimal Data-Dependent Hashing for Approximate Near Neighbors

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem

Siddharth Barman

Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem

Details
Discussion Comments: 0
Verification: Author has not verified information

Dimensionality Reduction for k-Means Clustering and Low Rank Approximation

Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu

Dimensionality Reduction for k-Means Clustering and Low Rank Approximation

Details
Discussion Comments: 0
Verification: Authors have not verified information

The List Decoding Radius of Reed-Muller Codes over Small Fields

Abhishek Bhowmick, Shachar Lovett

The List Decoding Radius of Reed-Muller Codes over Small Fields

Details
Discussion Comments: 0
Verification: Authors have not verified information

Excluded Grid Theorem: Improved and Simplified

Julia Chuzhoy

Excluded Grid Theorem: Improved and Simplified

Details
Discussion Comments: 0
Verification: Author has not verified information

Succinct Garbling and Indistinguishability Obfuscation for RAM Programs

Ran Canetti, Justin Holmgren, Abhishek Jain, Vinod Vaikuntanathan

Succinct Garbling and Indistinguishability Obfuscation for RAM Programs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximate Distance Oracles with Improved Bounds

Shiri Chechik

Approximate Distance Oracles with Improved Bounds

Details
Discussion Comments: 0
Verification: Author has not verified information

Efficiently Learning Ising Models on Arbitrary Graphs

Guy Bresler

Efficiently Learning Ising Models on Arbitrary Graphs

Details
Discussion Comments: 0
Verification: Author has not verified information

Quantum Spectrum Testing

Ryan O'Donnell, John Wright

Quantum Spectrum Testing

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Lovász Theta function for Independent Sets in Sparse Graphs

Nikhil Bansal, Anupam Gupta, Guru Guruganesh

On the Lovász Theta function for Independent Sets in Sparse Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Garbled RAM From One-Way Functions

Sanjam Garg, Steve Lu, Rafail Ostrovsky, Alessandra Scafuro

Garbled RAM From One-Way Functions

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Complexity of Nash Equilibria in Anonymous Games

Xi Chen, David Durfee, Anthi Orfanou

On the Complexity of Nash Equilibria in Anonymous Games

Details
Discussion Comments: 0
Verification: Authors have not verified information

Clustered Integer 3SUM via Additive Combinatorics

Timothy M. Chan, Moshe Lewenstein

Clustered Integer 3SUM via Additive Combinatorics

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Complexity of the Simplex Method

John Fearnley, Rahul Savani

The Complexity of the Simplex Method

Details
Discussion Comments: 0
Verification: Authors have not verified information

Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time

Ken-ichi Kawarabayashi, Mikkel Thorup

Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time

Details
Discussion Comments: 0
Verification: Authors have not verified information

Small Value Parallel Repetition for General Games

Mark Braverman, Ankit Garg

Small Value Parallel Repetition for General Games

Details
Discussion Comments: 0
Verification: Authors have not verified information

Inapproximability of Combinatorial Problems via Small LPs and SDPs

Gábor Braun, Sebastian Pokutta, Daniel Zink

Inapproximability of Combinatorial Problems via Small LPs and SDPs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Minimizing Flow-Time on Unrelated Machines

Nikhil Bansal, Janardhan Kulkarni

Minimizing Flow-Time on Unrelated Machines

Details
Discussion Comments: 0
Verification: Authors have not verified information

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

Arturs Backurs, Piotr Indyk

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

Details
Discussion Comments: 0
Verification: Authors have not verified information

Learning Mixtures of Gaussians in High Dimensions

Rong Ge, Qingqing Huang, Sham M. Kakade

Learning Mixtures of Gaussians in High Dimensions

Details
Discussion Comments: 0
Verification: Authors have not verified information

2-Server PIR with Sub-Polynomial Communication

Zeev Dvir, Sivakanth Gopi

2-Server PIR with Sub-Polynomial Communication

Details
Discussion Comments: 0
Verification: Authors have not verified information

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition

Irit Dinur, Prahladh Harsha, Guy Kindler

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition

Details
Discussion Comments: 0
Verification: Authors have not verified information

Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries

Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan

Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries

Details
Discussion Comments: 0
Verification: Authors have not verified information

Testing Cluster Structure of Graphs

Artur Czumaj, Pan Peng, Christian Sohler

Testing Cluster Structure of Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order

Nitish Korula, Vahab S. Mirrokni, Morteza Zadimoghaddam

Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order

Details
Discussion Comments: 0
Verification: Authors have not verified information

Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions

Shachar Lovett, Jiapeng Zhang

Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method

Andris Ambainis, Yuval Filmus, François Le Gall

Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method

Details
Discussion Comments: 0
Verification: Authors have not verified information

Rectangles Are Nonnegative Juntas

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman

Rectangles Are Nonnegative Juntas

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sparse Quantum Codes from Quantum Circuits

Dave Bacon, Steven T. Flammia, Aram Wettroth Harrow, Jonathan Shi

Sparse Quantum Codes from Quantum Circuits

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Characterization of the Capacity of Online (causal) Binary Channels

Zitan Chen, Sidharth Jaggi, Michael Langberg

A Characterization of the Capacity of Online (causal) Binary Channels

Details
Discussion Comments: 0
Verification: Authors have not verified information

Reed-Muller Codes for Random Erasures and Errors

Emmanuel Abbe, Amir Shpilka, Avi Wigderson

Reed-Muller Codes for Random Erasures and Errors

Details
Discussion Comments: 0
Verification: Authors have not verified information

An Interactive Information Odometer and Applications

Mark Braverman, Omri Weinstein

An Interactive Information Odometer and Applications

Details
Discussion Comments: 0
Verification: Authors have not verified information

From Independence to Expansion and Back Again

Tobias Christiani, Rasmus Pagh, Mikkel Thorup

From Independence to Expansion and Back Again

Details
Discussion Comments: 0
Verification: Authors have not verified information

Test-and-Set in Optimal Space

George Giakkoupis, Maryam Helmi, Lisa Higham, Philipp Woelfel

Test-and-Set in Optimal Space

Details
Discussion Comments: 0
Verification: Authors have not verified information

Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space

Jean Bourgain, Sjoerd Dirksen, Jelani Nelson

Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space

Details
Discussion Comments: 0
Verification: Authors have not verified information

Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian Sampling: Extended Abstract

Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz

Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian Sampling: Extended Abstract

Details
Discussion Comments: 0
Verification: Authors have not verified information

Randomized Composable Core-sets for Distributed Submodular Maximization

Vahab S. Mirrokni, Morteza Zadimoghaddam

Randomized Composable Core-sets for Distributed Submodular Maximization

Details
Discussion Comments: 0
Verification: Authors have not verified information

Nearly-Linear Time Positive LP Solver with Faster Convergence Rate

Zeyuan Allen Zhu, Lorenzo Orecchia

Nearly-Linear Time Positive LP Solver with Faster Convergence Rate

Details
Discussion Comments: 0
Verification: Authors have not verified information

High Parallel Complexity Graphs and Memory-Hard Functions

Joël Alwen, Vladimir Serbinenko

High Parallel Complexity Graphs and Memory-Hard Functions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms

Anand Louis

Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms

Details
Discussion Comments: 0
Verification: Author has not verified information

Analysis of a Classical Matrix Preconditioning Algorithm

Leonard J. Schulman, Alistair Sinclair

Analysis of a Classical Matrix Preconditioning Algorithm

Details
Discussion Comments: 0
Verification: Authors have not verified information

Random Permutations using Switching Networks

Artur Czumaj

Random Permutations using Switching Networks

Details
Discussion Comments: 0
Verification: Author has not verified information

An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm

Thomas Dueholm Hansen, Uri Zwick

An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection

Kyle Fox, Philip N. Klein, Shay Mozes

A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximating the Nash Social Welfare with Indivisible Items

Richard Cole, Vasilis Gkatzelis

Approximating the Nash Social Welfare with Indivisible Items

Details
Discussion Comments: 0
Verification: Authors have not verified information

Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity

Ittai Abraham, Danny Dolev

Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity

Details
Discussion Comments: 0
Verification: Authors have not verified information

Proof of the Satisfiability Conjecture for Large k

Jian Ding, Allan Sly, Nike Sun

Proof of the Satisfiability Conjecture for Large k

Details
Discussion Comments: 0
Verification: Authors have not verified information

How Well Can Graphs Represent Wireless Interference?

Magnús M. Halldórsson, Tigran Tonoyan

How Well Can Graphs Represent Wireless Interference?

Details
Discussion Comments: 0
Verification: Authors have not verified information

Secretary Problems with Non-Uniform Arrival Order

Thomas Kesselheim, Robert D. Kleinberg, Rad Niazadeh

Secretary Problems with Non-Uniform Arrival Order

Details
Discussion Comments: 0
Verification: Authors have not verified information