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

Vitaly Feldman and Jan Vondrak (IBM Almaden Research Center)**Approximate Modularity**

Flavio Chierichetti (Sapienza University), Abhimanyu Das (Google), Anirban Dasgupta (IIT Gandhinagar), Ravi Kumar (Google)**Approximating ATSP by Relaxing Connectivity**

Ola Svensson (EPFL)**Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP**

Nima Anari (UC Berkeley), Shayan Oveis Gharan (University of Washington)**An O(1)-Approximation for Minimum Spanning Tree Interdiction**

Rico Zenklusen (ETH Zurich)**Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line**

Amir Nayyeri (Oregon State University), Benjamin Raichel (University of Illinois, Urbana-Champaign)**Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem**

Bruce Shepherd, Adrian Vetta (McGill), Gordon Wilfong (Bell Labs)**Tight Hardness of the Non-commutative Grothendieck Problem**

Jop Briet (CWI), Oded Regev (NYU), Rishi Saket (IBM Research)**No Small Linear Program Approximates Vertex Cover within a Factor 2 - \epsilon**

Abbas Bazzi (EPFL), Samuel Fiorini (Universite libre de Bruxelles), Sebastian Pokutta (Georgia Tech), Ola Svensson (EPFL)**Hardness of Approximation in PSPACE and Separation Results for Pebble Games**

Siu Man Chan (University of Toronto), Massimo Lauria, Jakob Nordstrom, Marc Vinyals (KTH Royal Institute of Technology)**Lower Bounds for Clique vs. Independent Set**

Mika Göös (University of Toronto)**Deterministic Communication vs. Partition Number**

Mika Göös, Toniann Pitassi, and Thomas Watson (University of Toronto)**Welfare Maximization with Limited Interaction**

Noga Alon (Tel Aviv University and MSR Israel), Noam Nisan (Hebrew University and MSR Israel), Ran Raz (Weizmann Institue and IAS, Princeton), Omri Weinstein (Princeton University)**Near-optimal bounds on bounded-round quantum communication complexity of disjointness**

Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao (Princeton University), Dave Touchette (Université de Montréal)**Hamiltonian simulation with nearly optimal dependence on all parameters**

Dominic W. Berry (Macquarie University), Andrew M. Childs (University of Waterloo and University of Maryland), Robin Kothari (University of Waterloo and Massachusetts Institute of Technology)**Quantum Expander Codes**

Anthony Leverrier, Jean-Pierre Tillich (INRIA), Gilles Zémor (Bordeaux University)**An average-case depth hierarchy theorem for Boolean circuits**

Benjamin Rossman (NII, Tokyo and Simons Institute), Rocco A. Servedio (Columbia University), Li-Yang Tan (Simons Institute)**The Average Sensitivity of Bounded-Depth Formulas**

Benjamin Rossman (NII, Tokyo and Simons Institute)**The Power of Asymmetry in Constant-Depth Circuits**

Alexander Sherstov (UCLA)**Deterministic Divisibility Testing via Shifted Partial Derivatives**

Michael A. Forbes (Institute for Advanced Study)**The Complexity of General-Valued CSPs**

Vladimir Kolmogorov (IST Austria), Andrei Krokhin (Durham University, UK), Michal Rolinek (IST Austria)**Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable**

Helmut Seidl (TU München), Sebastian Maneth (University of Edinburgh), Gregor Kemper (TU München)**Tight Hardness Results for LCS and other Sequence Similarity Measures**

Amir Abboud (Stanford University), Arturs Backurs (MIT), Virginia Vassilevska Williams (Stanford University)**Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping**

Karl Bringmann (ETH Zurich), Marvin Künnemann (Max Planck Institute, Saarbrücken)**If the Current Clique Algorithms are Optimal, so is Valiant's Parser**

Amir Abboud (Stanford University), Arturs Backurs (MIT), Virginia Vassilevska Williams (Stanford University)**Uniform generation of random regular graphs**

Pu Gao (University of Waterloo), Nicholas Wormald (Monash University)**A Holant Dichotomy: Is the FKT Algorithm Universal?**

Jin-Yi Cai (University of Wisconsin-Madison), Zhiguo Fu (Jilin University), Heng Guo, Tyson Williams (University of Wisconsin-Madison)**Symbolic integration and the complexity of computing averages**

Leonard Schulman (Caltech), Alistair Sinclair (UC Berkeley), Piyush Srivastava (Caltech)**Community detection in the general stochastic block model: fundamental limits and efficient algorithms for recovery**

Emmanuel Abbe and Colin Sandon (Princeton University)**Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs**

Charles Bordenave (CNRS), Marc Lelarge (INRIA-ENS), Laurent Massoulie (INRIA-MSR)**How to refute a random CSP**

Sarah R. Allen, Ryan O'Donnell, and David Witmer (Carnegie Mellon University)**Black-Box Garbled RAM**

Sanjam Garg (UC Berkeley), Steve Lu (UCLA), and Rafail Ostrovsky (UCLA)**Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption**

Craig Gentry (IBM), Allison Bishop Lewko (Columbia University), Amit Sahai (UCLA), Brent Waters (University of Texas at Austin)**Indistinguishability Obfuscation from Functional Encryption**

Nir Bitansky and Vinod Vaikuntanathan (MIT)**Limits on the Power of Indistinguishability Obfuscation and Functional Encryption**

Gilad Asharov and Gil Segev (Hebrew University)**Optimal induced universal graphs and adjacency labeling for trees**

Stephen Alstrup, Søren Dahlgaard, and Mathias Bæk Tejs Knudsen (University of Copenhagen)**New Unconditional Hardness Results for Dynamic and Online Problems**

Raphael Clifford (Bristol University), Allan Grønlund (Aarhus University), Kasper Green Larsen (Aarhus University)**Towards an Optimal Method for Dynamic Planar Point Location**

Timothy M. Chan and Yakov Nekrich (University of Waterloo)**Pattern-avoiding access in binary search trees**

Parinya Chalermsook, Mayank Goswami (Max Planck Institute, Saarbrücken), Laszlo Kozma (Saarland University), Kurt Mehlhorn (Max-Planck Institute, Saarbrücken), Thatchaphol Saranurak (KTH Royal Institute of Technology)**Planar Reachability in Linear Space and Constant Time**

Jacob Holm, Eva Rotenberg, and Mikkel Thorup (University of Copenhagen)**The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication**

Erez Kantor (MIT), Zvi Lotker (Ben Gurion University), Merav Parter (Weizmann Institute), David Peleg (Weizmann Institute)**Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks**

John Augustine (IIT Madras), Gopal Pandurangan (University of Houston), Peter Robinson (Queen's University Belfast), Scott Roche (Northeastern University), Eli Upfal (Brown University)**Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems**

Barna Saha (University of Massachusetts Amherst)**Probabilistic Polynomials and Hamming Nearest Neighbors**

Josh Alman and Ryan Williams (Stanford University)**Breaking the Variance: Approximating the Hamming Distance in O~(1/\epsilon) Time Per Alignment**

Tsvi Kopelowitz (University of Michigan), Ely Porat (Bar Ilan University)**Efficient Inverse Maintenance and Faster Algorithms for Linear Programming**

Yin Tat Lee and Aaron Sidford (MIT)**A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization**

Yin Tat Lee (MIT), Aaron Sidford (MIT), Sam Chiu-wai Wong (UC Berkeley)**Solving the Closest Vector Problem in 2^n Time : The Discrete Gaussian Strikes Again!**

Divesh Aggarwal (EPFL), Daniel Dadush (CWI), Noah Stephens-Davidowitz (NYU)**Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time**

Yin Tat Lee (MIT), He Sun (University of Bristol)**FO Model Checking on Posets of Bounded Width**

Jakub Gajarsky (Masaryk University), Petr Hlineny (Masaryk University), Daniel Lokshtanov (University of Bergen), Jan Obdrzalek (Masaryk University), Sebastian Ordyniak (Masaryk University), M. S. Ramanujan (University of Bergen), Saket Saurabh (University of Bergen and IMSc Chennai)**Satisfiability of Ordering CSPs Above Average Is Fixed-Parameter Tractable**

Konstantin Makarychev (Microsoft Research), Yury Makarychev (TTI Chicago), Yuan Zhou (MIT)**Parameterizing the Permanent: genus, apices, minors, evaluation mod 2^k**

Radu Curticapean (Saarland University), Mingji Xia (Chinese Academy of Sciences)**On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms**

Xi Chen (Columbia University), Ilias Diakonikolas (University of Edinburgh), Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis (Columbia University)**On the Cryptographic Hardness of Finding a Nash Equilibrium**

Nir Bitansky (MIT), Omer Paneth (Boston University), Alon Rosen (IDC Herzliya)**Optimal Auction vs. Anonymous Pricing**

Saeed Alaei (Google Research), Jason Hartline (Northwestern University), Rad Niazadeh (Cornell University), Emmanouil Pountourakis (Northwestern University), Yang Yuan (Cornell University)**Noise-stable mixture selection, mechanism design and signaling**

Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng (USC)**Isomorphism Testing for Graphs of Bounded Rank Width**

Martin Grohe and Pascal Schweitzer (RWTH Aachen University)**A light metric spanner**

Lee-Ad Gottlieb (Ariel University)**Sample(x)=(a*x< =t) is a distinguisher with probability 1/8**

Mikkel Thorup (University of Copenhagen)**Hashing for statistics over k-partitions**

Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, and Mikkel Thorup (University of Copenhagen)**An algorithmic proof of the Lovasz Local Lemma via resampling oracles**

Nicholas Harvey (University of British Columbia), Jan Vondrak (IBM Almaden Research Center)**Incidences between points and lines in R^4**

Micha Sharir and Noam Solomon (Tel Aviv University)**Talagrand's convolution conjecture on Gaussian space**

Ronen Eldan and James R. Lee (University of Washington)**Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes**

Adam W. Marcus (Crisply, Yale University), Daniel A. Spielman (Yale University), Nikhil Srivastava (UC Berkeley)**Compressing and teaching for low VC-dimension**

Shay Moran (Technion), Amir Shpilka (Tel Aviv University), Avi Wigderson (IAS, Princeton), Amir Yehudayoff (Technion)**On the Structure, Covering, and Learning of Poisson Multinomial Distributions**

Constantinos Daskalakis, Gautam Kamath, Christos Tzamos (MIT)**Random Matrices: l1 Concentration and Dictionary Learning with Few Samples**

Kyle Luh and Van Vu (Yale University)**Guaranteed Matrix Completion via Non-convex Factorization**

Ruoyu Sun and Zhi-Quan Luo (University of Minnesota)**Heavy-tailed Independent Component Analysis**

Joseph Anderson (Ohio State University), Navin Goyal (Microsoft Research), Anupama Nandi, Luis Rademacher (Ohio State University)**Input Sparsity and Hardness for Robust Subspace Approximation**

Kenneth L. Clarkson and David P. Woodruff (IBM Almaden Research Center)**The Submodular Secretary Problem Goes Linear**

Moran Feldman (EPFL), Rico Zenklusen (ETH Zurich)**Competitive Flow Time Algorithms for Polyhedral Scheduling**

Sungjin Im (University of California, Merced), Janardhan Kulkarni, Kamesh Munagala (Duke University)**Online Buy-at-Bulk Network Design**

Deeparnab Chakrabarty (Microsoft Research), Alina Ene (University of Warwick), Ravishankar Krishnaswamy (Microsoft Research), Debmalya Panigrahi (Duke Univiersity)**Tight Bounds for Online Vector Scheduling**

Sungjin Im (University of California, Merced), Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi (Duke University)**Differentially Private Release and Learning of Threshold Functions**

Mark Bun (Harvard University), Kobbi Nissim (Ben-Gurion University and Harvard University), Uri Stemmer (Ben-Gurion University), Salil Vadhan (Harvard University)**Robust Traceability from Trace Amounts**

Cynthia Dwork (Microsoft Research), Adam Smith (Pennsylvania State University), Thomas Steinke (Harvard University), Jonathan Ullman (Columbia University), Salil Vadhan (Harvard University)**Local Correlation Breakers and Applications to Three-Source Extractors and Mergers**

Gil Cohen (Weizmann Institute of Science)**Three-Source Extractors for Polylogarithmic Min-Entropy**

Xin Li (Johns Hopkins University)**Beyond the central limit theorem: Asymptotic expansions and pseudorandomness for combinatorial sums**

Anindya De (IAS / DIMACS)**Pseudorandomness via the discrete Fourier transform**

Parikshit Gopalan (Microsoft Research), Daniel M. Kane (UC San Diego), Raghu Meka (UCLA)**On Monotonicity Testing and Boolean Isoperimetric type Theorems**

Subhash Khot (New York University), Dor Minzer, Muli Safra (Tel Aviv University)**Trading query complexity for sample-based testing and multi-testing scalability**

Eldar Fischer (Technion), Oded Lachish (Birkbeck, University of London), Yadu Vasudev (Technion)**Robust testing of lifted codes with applications to low-degree testing**

Alan Guo (MIT), Elad Haramaty (Northeastern University), Madhu Sudan (Microsoft Research)**Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions**

Ilias Diakonikolas (University of Edinburgh), Daniel Kane (UC San Diego), Vladimir Nikishkin (University of Edinburgh)**Approximately Counting Triangles in Sublinear Time**

Talya Eden, Amit Levi, Dana Ron (Tel Aviv University), C. Seshadhri (UC Santa Cruz)**A Robust Sparse Fourier Transform in the Continuous Setting**

Eric Price and Zhao Song (University of Texas at Austin)