IEEE Foundations of Computer Science, FOCS 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

Indistinguishability Obfuscation from Functional Encryption

Nir Bitansky, Vinod Vaikuntanathan

Indistinguishability Obfuscation from Functional Encryption

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

Symbolic Integration and the Complexity of Computing Averages

Leonard J. Schulman, Alistair Sinclair, Piyush Srivastava

Symbolic Integration and the Complexity of Computing Averages

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

How to Refute a Random CSP

Sarah R. Allen, Ryan O'Donnell, David Witmer

How to Refute a Random CSP

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

Lower Bounds for Clique vs. Independent Set

Mika Göös

Lower Bounds for Clique vs. Independent Set

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

Heavy-Tailed Independent Component Analysis

Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher

Heavy-Tailed Independent Component Analysis

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

Competitive Flow Time Algorithms for Polyhedral Scheduling

Sungjin Im, Janardhan Kulkarni, Kamesh Munagala

Competitive Flow Time Algorithms for Polyhedral Scheduling

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

The Power of Asymmetry in Constant-Depth Circuits

Alexander A. Sherstov

The Power of Asymmetry in Constant-Depth Circuits

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

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Yin Tat Lee, He Sun

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

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

Online Buy-at-Bulk Network Design

Alina Ene, Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Debmalya Panigrahi

Online Buy-at-Bulk Network Design

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

Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin

Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

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

The Submodular Secretary Problem Goes Linear

Moran Feldman, Rico Zenklusen

The Submodular Secretary Problem Goes Linear

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

A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization

Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong

A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization

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

Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions

Vitaly Feldman, Jan Vondrák

Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions

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

Approximately Counting Triangles in Sublinear Time

Talya Eden, Amit Levi, Dana Ron, C. Seshadhri

Approximately Counting Triangles in Sublinear Time

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

Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption

Craig Gentry, Allison Bishop Lewko, Amit Sahai, Brent Waters

Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption

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

Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems

Barna Saha

Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems

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

On Monotonicity Testing and Boolean Isoperimetric Type Theorems

Subhash Khot, Dor Minzer, Muli Safra

On Monotonicity Testing and Boolean Isoperimetric Type Theorems

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

Quantum Expander Codes

Anthony Leverrier, Jean-Pierre Tillich, Gilles Zémor

Quantum Expander Codes

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

On the Structure, Covering, and Learning of Poisson Multinomial Distributions

Constantinos Daskalakis, Gautam Kamath, Christos Tzamos

On the Structure, Covering, and Learning of Poisson Multinomial Distributions

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

Compressing and Teaching for Low VC-Dimension

Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff

Compressing and Teaching for Low VC-Dimension

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

Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping

Karl Bringmann, Marvin Künnemann

Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping

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

Tight Hardness of the Non-commutative Grothendieck Problem

Jop Briët, Oded Regev, Rishi Saket

Tight Hardness of the Non-commutative Grothendieck Problem

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

Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs

Charles Bordenave, Marc Lelarge, Laurent Massoulié

Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs

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

A Light Metric Spanner

Lee-Ad Gottlieb

A Light Metric Spanner

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

Optimal Induced Universal Graphs and Adjacency Labeling for Trees

Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen

Optimal Induced Universal Graphs and Adjacency Labeling for Trees

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

Probabilistic Polynomials and Hamming Nearest Neighbors

Josh Alman, Ryan Williams

Probabilistic Polynomials and Hamming Nearest Neighbors

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

An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles

Nicholas J. A. Harvey, Jan Vondrák

An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles

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

Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable

Helmut Seidl, Sebastian Maneth, Gregor Kemper

Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable

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

Robust Traceability from Trace Amounts

Cynthia Dwork, Adam D. Smith, Thomas Steinke, Jonathan Ullman, Salil P. Vadhan

Robust Traceability from Trace Amounts

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

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

Adam W. Marcus, Daniel A. Spielman, Nikhil Srivastava

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

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

Tight Bounds for Online Vector Scheduling

Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi

Tight Bounds for Online Vector Scheduling

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

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms

Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms

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

Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k

Radu Curticapean, Mingji Xia

Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k

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

Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem

F. Bruce Shepherd, Adrian Vetta, Gordon T. Wilfong

Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem

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

Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery

Emmanuel Abbe, Colin Sandon

Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery

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

Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP

Nima Anari, Shayan Oveis Gharan

Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP

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

Three-Source Extractors for Polylogarithmic Min-Entropy

Xin Li

Three-Source Extractors for Polylogarithmic Min-Entropy

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

Planar Reachability in Linear Space and Constant Time

Jacob Holm, Eva Rotenberg, Mikkel Thorup

Planar Reachability in Linear Space and Constant Time

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

Pseudorandomness via the Discrete Fourier Transform

Parikshit Gopalan, Daniek Kane, Raghu Meka

Pseudorandomness via the Discrete Fourier Transform

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

Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters

Dominic W. Berry, Andrew M. Childs, Robin Kothari

Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters

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

Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks

John Augustine, Gopal Pandurangan, Peter Robinson, Scott T. Roche, Eli Upfal

Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks

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

Efficient Inverse Maintenance and Faster Algorithms for Linear Programming

Yin Tat Lee, Aaron Sidford

Efficient Inverse Maintenance and Faster Algorithms for Linear Programming

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

A Robust Sparse Fourier Transform in the Continuous Setting

Eric Price, Zhao Song

A Robust Sparse Fourier Transform in the Continuous Setting

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

A Holant Dichotomy: Is the FKT Algorithm Universal?

Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams

A Holant Dichotomy: Is the FKT Algorithm Universal?

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

Differentially Private Release and Learning of Threshold Functions

Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan

Differentially Private Release and Learning of Threshold Functions

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

An O(1)-Approximation for Minimum Spanning Tree Interdiction

Rico Zenklusen

An O(1)-Approximation for Minimum Spanning Tree Interdiction

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

Sample (x) = (a*x<=t) is a Distinguisher with Probability 1/8

Mikkel Thorup

Sample (x) = (a*x<=t) is a Distinguisher with Probability 1/8

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

The Complexity of General-Valued CSPs

Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolinek

The Complexity of General-Valued CSPs

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

Deterministic Communication vs. Partition Number

Mika Göös, Toniann Pitassi, Thomas Watson

Deterministic Communication vs. Partition Number

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

Pattern-Avoiding Access in Binary Search Trees

Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak

Pattern-Avoiding Access in Binary Search Trees

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

Approximate Modularity

Flavio Chierichetti, Abhimanyu Das, Anirban Dasgupta, Ravi Kumar

Approximate Modularity

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

Mixture Selection, Mechanism Design, and Signaling

Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng

Mixture Selection, Mechanism Design, and Signaling

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

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, Ola Svensson

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

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

Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums

Anindya De

Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums

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

Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!

Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz

Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!

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

The Average Sensitivity of Bounded-Depth Formulas

Benjamin Rossman

The Average Sensitivity of Bounded-Depth Formulas

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

New Unconditional Hardness Results for Dynamic and Online Problems

Raphaël Clifford, Allan Grønlund, Kasper Green Larsen

New Unconditional Hardness Results for Dynamic and Online Problems

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

Towards an Optimal Method for Dynamic Planar Point Location

Timothy M. Chan, Yakov Nekrich

Towards an Optimal Method for Dynamic Planar Point Location

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

Black-Box Garbled RAM

Sanjam Garg, Steve Lu, Rafail Ostrovsky

Black-Box Garbled RAM

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

Optimal Auctions vs. Anonymous Pricing

Saeed Alaei, Jason D. Hartline, Rad Niazadeh, Emmanouil Pountourakis, Yang Yuan

Optimal Auctions vs. Anonymous Pricing

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

Input Sparsity and Hardness for Robust Subspace Approximation

Kenneth L. Clarkson, David P. Woodruff

Input Sparsity and Hardness for Robust Subspace Approximation

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

Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable

Konstantin Makarychev, Yury Makarychev, Yuan Zhou

Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable

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

Guaranteed Matrix Completion via Nonconvex Factorization

Ruoyu Sun, Zhi-Quan Luo

Guaranteed Matrix Completion via Nonconvex Factorization

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

Uniform Generation of Random Regular Graphs

Pu Gao, Nicholas C. Wormald

Uniform Generation of Random Regular Graphs

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

The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication

Erez Kantor, Zvi Lotker, Merav Parter, David Peleg

The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication

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

Isomorphism Testing for Graphs of Bounded Rank Width

Martin Grohe, Pascal Schweitzer

Isomorphism Testing for Graphs of Bounded Rank Width

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

Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness

Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette

Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness

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

An Average-Case Depth Hierarchy Theorem for Boolean Circuits

Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan

An Average-Case Depth Hierarchy Theorem for Boolean Circuits

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

Talagrand's Convolution Conjecture on Gaussian Space

Ronen Eldan, James R. Lee

Talagrand's Convolution Conjecture on Gaussian Space

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

FO Model Checking on Posets of Bounded Width

Jakub Gajarský, Petr Hlinený, Daniel Lokshtanov, Jan Obdrzálek, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh

FO Model Checking on Posets of Bounded Width

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

Random Matrices: l1 Concentration and Dictionary Learning with Few Samples

Kyle Luh, Van Vu

Random Matrices: l1 Concentration and Dictionary Learning with Few Samples

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

Incidences between Points and Lines in R^4

Micha Sharir, Noam Solomon

Incidences between Points and Lines in R^4

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

Breaking the Variance: Approximating the Hamming Distance in 1/ε Time Per Alignment

Tsvi Kopelowitz, Ely Porat

Breaking the Variance: Approximating the Hamming Distance in 1/ε Time Per Alignment

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

Hashing for Statistics over K-Partitions

Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup

Hashing for Statistics over K-Partitions

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

Approximating ATSP by Relaxing Connectivity

Ola Svensson

Approximating ATSP by Relaxing Connectivity

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

Deterministic Divisibility Testing via Shifted Partial Derivatives

Michael A. Forbes

Deterministic Divisibility Testing via Shifted Partial Derivatives

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

Local Correlation Breakers and Applications to Three-Source Extractors and Mergers

Gil Cohen

Local Correlation Breakers and Applications to Three-Source Extractors and Mergers

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

Welfare Maximization with Limited Interaction

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein

Welfare Maximization with Limited Interaction

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

Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability

Eldar Fischer, Oded Lachish, Yadu Vasudev

Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability

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

Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line

Amir Nayyeri, Benjamin Raichel

Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line

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

If the Current Clique Algorithms are Optimal, So is Valiant's Parser

Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams

If the Current Clique Algorithms are Optimal, So is Valiant's Parser

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

Limits on the Power of Indistinguishability Obfuscation and Functional Encryption

Gilad Asharov, Gil Segev

Limits on the Power of Indistinguishability Obfuscation and Functional Encryption

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

On the Cryptographic Hardness of Finding a Nash Equilibrium

Nir Bitansky, Omer Paneth, Alon Rosen

On the Cryptographic Hardness of Finding a Nash Equilibrium

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

Tight Hardness Results for LCS and Other Sequence Similarity Measures

Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams

Tight Hardness Results for LCS and Other Sequence Similarity Measures

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

Robust Testing of Lifted Codes with Applications to Low-Degree Testing

Alan Guo, Elad Haramaty, Madhu Sudan

Robust Testing of Lifted Codes with Applications to Low-Degree Testing

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

Hardness of Approximation in PSPACE and Separation Results for Pebble Games

Siu Man Chan, Massimo Lauria, Jakob Nordström, Marc Vinyals

Hardness of Approximation in PSPACE and Separation Results for Pebble Games

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