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

Session 1.3A

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

by Eshan Chattopadhyay, Xin Li

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

by Xin Li

Extractors for Near Logarithmic Min-Entropy

by Gil Cohen, Leonard J. Schulman

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

by Gil Cohen

The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling

by Zachary Remscrim

Session 1.3B

Computational Efficiency Requires Simple Taxation

by Shahar Dobzinski

Learning in Auctions: Regret is Hard, Envy is Easy

by Constantinos Daskalakis, Vasilis Syrgkanis

On the Communication Complexity of Approximate Fixed Points

by Tim Roughgarden, Omri Weinstein

Informational Substitutes

by Yiling Chen, Bo Waggoner

Constrained Submodular Maximization: Beyond 1/e

by Alina Ene, Huy L. Nguy?n

Session 1.4 Best Papers

Settling the Complexity of Computing Approximate Two-Player Nash Equilibria

by Aviad Rubinstein

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

by Ran Raz

Ramanujan Graphs in Polynomial Time

by Michael B. Cohen

Session 2.1A

Structure of Protocols for XOR Functions

by Hamed Hatami, Kaave Hosseini, Shachar Lovett

The Multiparty Communication Complexity of Interleaved Group Products

by W.T. Gowers, Emanuele Viola

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

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

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

by Omri Weinstein, Huacheng Yu

Session 2.1B

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

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

Fully Dynamic Maximal Matching in Constant Update Time

by Shay Solomon

On Fully Dynamic Graph Sparsifiers

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

Linear Hashing Is Awesome

by Mathias Bæk Tejs Knudsen

Session 2.2

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

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

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

by Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour

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

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

Session 2.3

Knuth Prize Lecture: Complexity of Communication in Markets

by Noam Nisan

Session 2.4

No Occurrence Obstructions in Geometric Complexity Theory

by Peter Bürgisser, Christian Ikenmeyer, Greta Panova

Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory

by Christian Ikenmeyer, Greta Panova

Exponential Lower Bounds for Monotone Span Programs

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

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

by Haris Aziz, Simon Mackenzie

Session 2.5A

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

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

Polynomial-Time Tensor Decompositions with Sum-of-Squares

by Tengyu Ma, Jonathan Shi, David Steurer

Towards Strong Reverse Minkowski-Type Inequalities for Lattices

by Daniel Dadush, Oded Regev

Session 2.5B

Which Regular Expression Patterns Are Hard to Match?

by Arturs Backurs, Piotr Indyk

Polynomial Representations of Threshold Functions and Algorithmic Applications

by Josh Alman, Timothy M. Chan, Ryan Williams

by Amir Abboud, Søren Dahlgaard

Session 2.6A

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

by Ryan Rogers, Aaron Roth, Adam Smith, Om Thakkar

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

by Sofya Raskhodnikova, Adam Smith

Session 2.6B

The Constant Inapproximability of the Parameterized Dominating Set Problem

by Yijia Chen, Bingkai Lin

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

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

Testing Assignments to Constraint Satisfaction Problems

by Hubie Chen, Matt Valeriote, Yuichi Yoshida

Session 3.1A

Compressing Interactive Communication under Product Distributions

by Alexander A. Sherstov

Decidability of Non-interactive Simulation of Joint Distributions

by Badih Ghazi, Pritish Kamath, Madhu Sudan

Separations in Communication Complexity Using Cheat Sheets and Information Complexity

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

Extension Complexity of Independent Set Polytopes

by Mika Göös, Rahul Jain, Thomas Watson

Session 3.1B

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

by Rasmus Kyng, Sushant Sachdeva

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

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

Computing Maximum Flow with Augmenting Electrical Flows

by Aleksander Madry

Optimizing Star-Convex Functions

by Jasper C.H. Lee, Paul Valiant

Session 3.2A

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

by Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie

Local Conflict Coloring

by Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski

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

by David R. Karger

A New Framework for Distributed Submodular Maximization

by Rafael Da Ponte Barbosa, Alina Ene, Huy L. Nguyễn, Justin Ward

Session 3.2B

Robust Estimators in High Dimensions without the Computational Intractability

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

Agnostic Estimation of Mean and Covariance

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

Noisy Population Recovery in Polynomial Time

by Anindya De, Michael Saks, Sijian Tang

A New Approach for Testing Properties of Discrete Distributions

by Ilias Diakonikolas, Daniel M. Kane

Session 3.3A

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

by Felix Joos, Guillem Perarnau, Dieter Rautenbach, Bruce Reed

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

by Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovic, Eric Vigoda, Yitong Yin

Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing

by Elizabeth Crosson, Aram W. Harrow

The Number of Solutions for Random Regular NAE-SAT

by Allan Sly, Nike Sun, Yumeng Zhang

Session 3.3B

Accelerated Newton Iteration for Roots of Black Box Polynomials

by Anand Louis, Santosh S. Vempala

Fourier-Sparse Interpolation without a Frequency Gap

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

Robust Fourier and Polynomial Curve Fitting

by Venkatesan Guruswami, David Zuckerman

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

by Venkata Gandikota, Badih Ghazi, Elena Grigorescu

Session 3.4A

Amplification and Derandomization without Slowdown

by Ofer Grossman, Dana Moshkovitz

Commutativity in the Algorithmic Lovász Local Lemma

by Vladimir Kolmogorov

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

by Nikhil Bansal, Daniel Dadush, Shashwat Garg

Session 3.4B

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

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

A PTAS for the Steiner Forest Problem in Doubling Metrics

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

On Approximating Maximum Independent Set of Rectangles

by Julia Chuzhoy, Alina Ene

Sponsored by

2016 IEEE 57th Annual Symposium on Foundations of Computer Science

New Brunswick, New Jersey

9-11 October 2016

Conference Information

Papers By Session