Efficient Inverse Maintenance and Faster Algorithms for Linear Programming

Yin Tat Lee, Aaron Sidford

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

Erez Kantor, Zvi Lotker, Merav Parter, David Peleg

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Yin Tat Lee, He Sun

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

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

Guaranteed Matrix Completion via Non-convex Factorization

Ruoyu Sun, Zhi-Quan Luo

Planar Reachability in Linear Space and Constant Time

Jacob Holm, Eva Rotenberg, Mikkel Thorup

Heavy-tailed Independent Component Analysis

Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher,

Towards an Optimal Method for Dynamic Planar Point Location

Timothy M. Chan, Yakov Nekrich

Input Sparsity and Hardness for Robust Subspace Approximation

Kenneth L. Clarkson, David P. Woodruff

Pattern-avoiding access in binary search trees

Parinya Chalermsook, Mayank Goswami, Laszlo Kozma, Kurt Mehlhorn, Thatchaphol Saranurak

The Average Sensitivity of Bounded-Depth Formulas

Benjamin Rossman

The Submodular Secretary Problem Goes Linear

Moran Feldman, Rico Zenklusen

The Power of Asymmetry in Constant-Depth Circuits

Alexander A. Sherstov

Competitive Flow Time Algorithms for Polyhedral Scheduling

Sungjin Im, Janardhan Kulkarni, Kamesh Munagala

Deterministic Divisibility Testing via Shifted Partial Derivatives

Michael A. Forbes

Tight Bounds for Online Vector Scheduling

Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi

Hardness of Approximation in PSPACE and Separation Results for Pebble Games

Siu Man Chan, Massimo Lauria, Jakob Nordstrom, Marc Vinyals

Online Buy-at-Bulk Network Design

Alina Ene, Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Debmalya Panigrahi

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

Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz

Differentially Private Release and Learning of Threshold Functions

Mark Bun, Kobbi Nissim, Uri Stemmer, Salil Vadhan

A Robust Sparse Fourier Transform in the Continuous Setting

Eric Price, Zhao Song

Robust Traceability from Trace Amounts

Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, Salil Vadhan

Breaking the Variance: Approximating the Hamming Distance in O~{1/\epsilon} Time Per Alignment

Tsvi Kopelowitz ,Ely Porat

Community detection in the general stochastic block model: fundamental limits and efficient algorithms for recovery

Emmanuel Abbe, Colin Sandon

Approximately Counting Triangles in Sublinear Time

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

How to refute a random CSP

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

An O{1}-Approximation for Minimum Spanning Tree Interdiction

Rico Zenklusen

Near-optimal bounds on bounded-round quantum communication complexity of disjointness

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

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

Amir Nayyeri, Benjamin Raichel

Hamiltonian simulation with nearly optimal dependence on all parameters

Dominic William Berry, Andrew MacGregor Childs, Robin Kothari

Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem

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

Quantum Expander Codes

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

A light metric spanner

Lee-Ad Gottlieb

Robust testing of lifted codes with applications to low-degree testing

Alan Guo, Elad Haramaty, Madhu Sudan

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

Gil Cohen

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

Helmut Seidl, Sebastian Maneth, Gregor Kemper

Three-Source Extractors for Polylogarithmic Min-Entropy

Xin Li

FO Model Checking on Posets of Bounded Width

Jakub Gajarsky, Petr Hlineny, Daniel Lokshtanov, Jan Obdrzalek, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh

Beyond the central limit theorem: Asymptotic expansions and pseudorandomness for combinatorial sums

Anindya De

Satisfiability of Ordering CSPs Above Average Is Fixed-Parameter Tractable

Konstantin Makarychev, Yury Makarychev, Yuan Zhou

Pseudorandomness via the discrete Fourier transform

Parikshit Gopalan, Daniel Kane, Raghu Meka

Parameterizing the Permanent: genus, apices, minors, evaluation mod 2^k

Radu Curticapean, Mingji Xia

Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions

Vitaly Feldman, Jan Vondrak

Isomorphism Testing for Graphs of Bounded Rank Width

Martin Grohe, Pascal Schweitzer

An average-case depth hierarchy theorem for Boolean circuits

[best paper award]

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

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

[best student paper award]

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

Lower Bounds for Clique vs. Independent Set

[best student paper award]

Mika Göös

Deterministic Communication vs. Partition Number

Mika Göös, Toniann Pitassi, Thomas Watson

Approximate Modularity

Flavio Chiericetti, Abhimanyu Das, Anirban Dasgupta, Ravi Kumar

New Unconditional Hardness Results for Dynamic and Online Problems

Raphael Clifford. Allan Gronlund, Kasper Green Larsen

Trading query complexity for sample-based testing and multi-testing scalability

Eldar Fischer, Oded Lachish, Yadu Vasudev

Tight Hardness of the Non-commutative Grothendieck Problem

Jop Briet, Oded Regev, Rishi Saket

Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin

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

Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, Ola Svensson

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

Constantinos Daskalakis, Gautam Kamath, Christos Tzamos

Uniform generation of random regular graphs

Pu Gao, Nicholas Wormald

Sample{x}={a*x< =t} is a distinguisher with probability 1/8

Mikkel Thorup

Symbolic integration and the complexity of computing averages

Leonard J. Schulman, Alistair Sinclair, Piyush Srivastava

Hashing for statistics over k-partitions

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

The Complexity of General-Valued CSPs

Vladimir Kolmogorov, Andrei Krokhin, Michal Rolinek

Optimal induced universal graphs and adjacency labeling for trees

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

A Holant Dichotomy: Is the FKT Algorithm Universal?

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

An algorithmic proof of the Lovasz Local Lemma via resampling oracles

Nicholas J. A. Harvey, Jan Vondrak

Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs

Charles Bordenave, Marc Lelarge, Laurent Massoulie

Mixture Selection, Mechanism Design, and Signaling

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

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

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

Optimal Auction vs. Anonymous Pricing

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

Incidences between points and lines in R^4

Micha Sharir, Noam Solomon

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms

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

Talagrand's convolution conjecture on Gaussian space

Ronen Eldan, James R. Lee

On the Cryptographic Hardness of Finding a Nash Equilibrium

Nir Bitansky, Omer Paneth, Alon Rosen

Random Matrices: l1 Concentration and Dictionary Learning with Few Samples

Kyle Luh, Van Vu

Welfare Maximization with Limited Interaction

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein