IEEE Foundations of Computer Science, FOCS 2016


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

Robust Estimators in High Dimensions without the Computational Intractability

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart

Robust Estimators in High Dimensions without the Computational Intractability

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

Commutativity in the Algorithmic Lovász Local Lemma

Vladimir Kolmogorov

Commutativity in the Algorithmic Lovász Local Lemma

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

Extension Complexity of Independent Set Polytopes

Mika Göös, Rahul Jain, Thomas Watson

Extension Complexity of Independent Set Polytopes

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

A New Framework for Distributed Submodular Maximization

Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen, Justin Ward

A New Framework for Distributed Submodular Maximization

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

Optimizing Star-Convex Functions

Jasper C. H. Lee, Paul Valiant

Optimizing Star-Convex Functions

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

Strong Fooling Sets for Multi-player Communication with Applications to Deterministic Estimation of Stream Statistics

Amit Chakrabarti, Sagar Kale

Strong Fooling Sets for Multi-player Communication with Applications to Deterministic Estimation of Stream Statistics

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

Simulated Quaotum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing

Elizabeth Crosson, Aram Wettroth Harrow

Simulated Quaotum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing

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

Compressing Interactive Communication under Product Distributions

Alexander A. Sherstov

Compressing Interactive Communication under Product Distributions

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

Agnostic Estimation of Mean and Covariance

Kevin A. Lai, Anup B. Rao, Santosh Vempala

Agnostic Estimation of Mean and Covariance

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

Informational Substitutes

Yiling Chen, Bo Waggoner

Informational Substitutes

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

A PTAS for the Steiner Forest Problem in Doubling Metrics

T.-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang

A PTAS for the Steiner Forest Problem in Doubling Metrics

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

Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product

Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams

Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product

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

Learning in Auctions: Regret is Hard, Envy is Easy

Constantinos Daskalakis, Vasilis Syrgkanis

Learning in Auctions: Regret is Hard, Envy is Easy

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

An Average-Case Depth Hierarchy Theorem for Higher Depth

Johan Håstad

An Average-Case Depth Hierarchy Theorem for Higher Depth

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

Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform Distributions

Sungjin Im, Shi Li

Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform Distributions

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

Noisy Population Recovery in Polynomial Time

Anindya De, Michael E. Saks, Sijian Tang

Noisy Population Recovery in Polynomial Time

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

Knuth Prize Lecture: Complexity of Communication in Markets

Noam Nisan

Knuth Prize Lecture: Complexity of Communication in Markets

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

Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification Protocols

Eshan Chattopadhyay, Xin Li

Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification Protocols

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

Structure of Protocols for XOR Functions

Hamed Hatami, Kaave Hosseini, Shachar Lovett

Structure of Protocols for XOR Functions

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

Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model

Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda, Yitong Yin

Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model

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

Decidability of Non-interactive Simulation of Joint Distributions

Badih Ghazi, Pritish Kamath, Madhu Sudan

Decidability of Non-interactive Simulation of Joint Distributions

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)

Susanna F. de Rezende, Jakob Nordström, Marc Vinyals

How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)

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

Zero-Knowledge Proof Systems for QMA

Anne Broadbent, Zhengfeng Ji, Fang Song, John Watrous

Zero-Knowledge Proof Systems for QMA

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

Constrained Submodular Maximization: Beyond 1/e

Alina Ene, Huy L. Nguyen

Constrained Submodular Maximization: Beyond 1/e

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

The Multiparty Communication Complexity of Interleaved Group Products

W. T. Gowers, Emanuele Viola

The Multiparty Communication Complexity of Interleaved Group Products

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

Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More

Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu

Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More

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

Extractors for Near Logarithmic Min-Entropy

Gil Cohen, Leonard J. Schulman

Extractors for Near Logarithmic Min-Entropy

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

Local Search Yields a PTAS for k-Means in Doubling Metrics

Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour

Local Search Yields a PTAS for k-Means in Doubling Metrics

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

Accelerated Newton Iteration for Roots of Black Box Polynomials

Anand Louis, Santosh Srinivas Vempala

Accelerated Newton Iteration for Roots of Black Box Polynomials

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

Bounded-Communication Leakage Resilience via Parity-Resilient Circuits

Vipul Goyal, Yuval Ishai, Hemanta K. Maji, Amit Sahai, Alexander A. Sherstov

Bounded-Communication Leakage Resilience via Parity-Resilient Circuits

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

Settling the Complexity of Computing Approximate Two-Player Nash Equilibria

Aviad Rubinstein

Settling the Complexity of Computing Approximate Two-Player Nash Equilibria

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

Online Algorithms for Covering and Packing Problems with Convex Objectives

Yossi Azar, Niv Buchbinder, T.-H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, Debmalya Panigrahi

Online Algorithms for Covering and Packing Problems with Convex Objectives

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

An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound

Nikhil Bansal, Daniel Dadush, Shashwat Garg

An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound

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

How to Determine if a Random Graph with a Fixed Degree Sequence Has a Giant Component

Felix Joos, Guillem Perarnau, Dieter Rautenbach, Bruce A. Reed

How to Determine if a Random Graph with a Fixed Degree Sequence Has a Giant Component

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

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

Haris Aziz, Simon Mackenzie

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

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

No Occurrence Obstructions in Geometric Complexity Theory

Peter Bürgisser, Christian Ikenmeyer, Greta Panova

No Occurrence Obstructions in Geometric Complexity Theory

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

Max-Information, Differential Privacy, and Post-selection Hypothesis Testing

Ryan M. Rogers, Aaron Roth, Adam D. Smith, Om Thakkar

Max-Information, Differential Privacy, and Post-selection Hypothesis Testing

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism

Sofya Raskhodnikova, Adam D. Smith

Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism

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

Depth-Reduction for Composites

Shiteng Chen, Periklis A. Papakonstantinou

Depth-Reduction for Composites

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

Breaking the Three Round Barrier for Non-malleable Commitments

Vipul Goyal, Dakshita Khurana, Amit Sahai

Breaking the Three Round Barrier for Non-malleable Commitments

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

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

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

The Number of Solutions for Random Regular NAE-SAT

Allan Sly, Nike Sun, Yumeng Zhang

The Number of Solutions for Random Regular NAE-SAT

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

Towards Strong Reverse Minkowski-Type Inequalities for Lattices

Daniel Dadush, Oded Regev

Towards Strong Reverse Minkowski-Type Inequalities for Lattices

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

The Constant Inapproximability of the Parameterized Dominating Set Problem

Yijia Chen, Bingkai Lin

The Constant Inapproximability of the Parameterized Dominating Set Problem

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

Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication

Omri Weinstein, Huacheng Yu

Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication

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

Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory

Christian Ikenmeyer, Greta Panova

Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory

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

Edit Distance: Sketching, Streaming, and Document Exchange

Djamal Belazzougui, Qin Zhang

Edit Distance: Sketching, Streaming, and Document Exchange

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

Local Conflict Coloring

Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski

Local Conflict Coloring

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

A New Approach for Testing Properties of Discrete Distributions

Ilias Diakonikolas, Daniel M. Kane

A New Approach for Testing Properties of Discrete Distributions

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

Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple

Rasmus Kyng, Sushant Sachdeva

Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple

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

Separations in Communication Complexity Using Cheat Sheets and Information Complexity

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

Separations in Communication Complexity Using Cheat Sheets and Information Complexity

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

Exponential Lower Bounds for Monotone Span Programs

Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook

Exponential Lower Bounds for Monotone Span Programs

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

Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms

Amir Abboud, Søren Dahlgaard

Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms

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

Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy

Xin Li

Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy

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

Polynomial Representations of Threshold Functions and Algorithmic Applications

Josh Alman, Timothy M. Chan, R. Ryan Williams

Polynomial Representations of Threshold Functions and Algorithmic Applications

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

Polynomial-Time Tensor Decompositions with Sum-of-Squares

Tengyu Ma, Jonathan Shi, David Steurer

Polynomial-Time Tensor Decompositions with Sum-of-Squares

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

Optimal Quantile Approximation in Streams

Zohar S. Karnin, Kevin J. Lang, Edo Liberty

Optimal Quantile Approximation in Streams

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

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering

Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering

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

Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning

Ran Raz

Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning

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

On the Communication Complexity of Approximate Fixed Points

Tim Roughgarden, Omri Weinstein

On the Communication Complexity of Approximate Fixed Points

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

Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths

Michael Elkin, Ofer Neiman

Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths

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

Which Regular Expression Patterns Are Hard to Match?

Arturs Backurs, Piotr Indyk

Which Regular Expression Patterns Are Hard to Match?

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

A Fast and Simple Unbiased Estimator for Network (Un)reliability

David R. Karger

A Fast and Simple Unbiased Estimator for Network (Un)reliability

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

Computational Efficiency Requires Simple Taxation

Shahar Dobzinski

Computational Efficiency Requires Simple Taxation

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

Computing Maximum Flow with Augmenting Electrical Flows

Aleksander Madry

Computing Maximum Flow with Augmenting Electrical Flows

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

Robust Fourier and Polynomial Curve Fitting

Venkatesan Guruswami, David Zuckerman

Robust Fourier and Polynomial Curve Fitting

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

Heavy Hitters via Cluster-Preserving Clustering

Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup

Heavy Hitters via Cluster-Preserving Clustering

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

Testing Assignments to Constraint Satisfaction Problems

Hubie Chen, Matthew Valeriote, Yuichi Yoshida

Testing Assignments to Constraint Satisfaction Problems

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

Fourier-Sparse Interpolation without a Frequency Gap

Xue Chen, Daniel M. Kane, Eric Price, Zhao Song

Fourier-Sparse Interpolation without a Frequency Gap

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

NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem

Venkata Gandikota, Badih Ghazi, Elena Grigorescu

NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem

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

Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness

Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers

Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness

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

On Fully Dynamic Graph Sparsifiers

Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, Richard Peng

On Fully Dynamic Graph Sparsifiers

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

Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics

Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu

Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics

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

An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model

Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie

An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model

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

Fully Dynamic Maximal Matching in Constant Update Time

Shay Solomon

Fully Dynamic Maximal Matching in Constant Update Time

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

Linear Hashing Is Awesome

Mathias Bæk Tejs Knudsen

Linear Hashing Is Awesome

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

Amplification and Derandomization without Slowdown

Ofer Grossman, Dana Moshkovitz

Amplification and Derandomization without Slowdown

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

On Approximating Maximum Independent Set of Rectangles

Julia Chuzhoy, Alina Ene

On Approximating Maximum Independent Set of Rectangles

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

Ramanujan Graphs in Polynomial Time

Michael B. Cohen

Ramanujan Graphs in Polynomial Time

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

Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time

Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Lacki, Nikos Parotsidis

Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Making the Most of Advice: New Correlation Breakers and Their Applications

Gil Cohen

Making the Most of Advice: New Correlation Breakers and Their Applications

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

Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings

Huijia Lin, Vinod Vaikuntanathan

Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings

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

A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function

Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov

A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function

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

A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing

Ankit Garg, Leonid Gurvits, Rafael Oliveira, Avi Wigderson

A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing

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

The Salesman's Improved Paths: A 3/2+1/34 Approximation

András Sebö, Anke van Zuylen

The Salesman's Improved Paths: A 3/2+1/34 Approximation

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

The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling

Zachary Remscrim

The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling

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