**Computing with Tangles.**

Martin Grohe (RWTH Aachen University) and Pascal Schweitzer (RWTH Aachen University)**Quantum Spectrum Testing.**

Ryan O'Donnell (Carnegie Mellon University); John Wright (Carnegie Mellon University)**The Directed Grid Theorem.**

Ken-ichi Kawarabayashi (National Institute of Informatics and JST ERATO) and Stephan Kreutzer (Technical University Berlin)**Test-and-Set in Optimal Space.**

George Giakkoupis (INRIA Rennes); Maryam Helmi (University of Calgary); Lisa Higham (University of Calgary); Philipp Woelfel (University of Calgary)**l_p Row Sampling by Lewis Weights.**

Michael B. Cohen (MIT) and Richard Peng (MIT)**Rectangles Are Nonnegative Juntas.**

Mika Göös (University of Toronto); Shachar Lovett (University of California, San Diego); Raghu Meka (University of California, Los Angeles); Thomas Watson (University of Toronto); David Zuckerman (University of Texas at Austin)**Garbled RAM From One-Way Functions.**

Sanjam Garg (UC Berkeley), Steve Lu (UCLA), Rafail Ostrovsky (UCLA), Alessandra Scafuro (Boston University and Northeastern University)**Testing Cluster Structure of Graphs.**

Artur Czumaj (University of Warwick), Pan Peng (TU Dortmund and Chinese Academy of Sciences), Christian Sohler (TU Dortmund)**The Complexity of the Simplex Method.**

John Fearnley (University of Liverpool); Rahul Savani (University of Liverpool);**Greedy Algorithms for Steiner Forest.**

Anupam Gupta (Carnegie Mellon University) and Amit Kumar (IIT Delhi)**Inapproximability of Nash Equilibrium.**

Aviad Rubinstein (UC Berkeley)**Non-malleable Reductions and Applications.**

Divesh Aggarwal (EPFL), Yevgeniy Dodis (NYU), Tomasz Kazana (University of Warsaw), Maciej Obremski (University of Warsaw)**Approximate k-flat Nearest Neighbor Search.**

Wolfgang Mulzer (FU Berlin); Huy L. Nguyen (Simons Institute); Paul Seiferth (FU Berlin); Yannik Stein (FU Berlin)**Sparse Quantum Codes from Quantum Circuits.**

Dave Bacon (University of Washington and Google), Steven T. Flammia (U Sydney), Aram W. Harrow (MIT), Jonathan Shi (Cornell)**Minimizing Flow-Time on Unrelated Machines.**

Nikhil Bansal (Eindhoven University of Technology, Netherlands); Janardhan Kulkarni (Duke University)**Prioritized Metric Structures and Embedding.**

Michael Elkin (Ben-Gurion University of the Negev); Arnold Filtser (Ben-Gurion University of the Negev); Neiman Ofer (Ben-Gurion University of the Negev)**Random permutations using switching networks.**

Artur Czumaj (University of Warwick)**From Independence to Expansion and Back Again.**

Tobias Christiani (IT University of Copenhagen); Rasmus Pagh (IT University of Copenhagen); Mikkel Thorup (University of Copenhagen);**FPTAS for #BIS with Degree Bounds on One Side.**

Jingcheng Liu (UC Berkeley), Pinyan Lu (Microsoft Research)**Excluded Grid Theorem: Improved and Simplified.**

Julia Chuzhoy (Toyota Technological Institute at Chicago)**2-Server PIR with sub-polynomial communication.**

Zeev Dvir (Princeton University) and Sivakanth Gopi (Princeton University)**Sum-of-squares lower bounds for planted clique.**

Raghu Meka (UCLA), Aaron Potechin (MIT), Avi Wigderson (IAS)**Reed-Muller codes for random erasures and errors.**

Emmanuel Abbe (Princeton University); Amir Shpilka (Tel-Aviv University); Avi Wigderson (IAS, Princeton).**Sketching and Embedding are Equivalent for Norms.**

Alexandr Andoni (Simons Institute); Robert Krauthgamer (Weizmann Institute of Science); Ilya Razenshteyn (MIT)**Clustered Integer 3SUM via Additive Combinatorics.**

Timothy M. Chan (University of Waterloo); Moshe Lewenstein (Bar-Ilan University)**Small value parallel repetition for general games.**

Mark Braverman (Princeton University); Ankit Garg (Princeton University).**Approximate Distance Oracles with Improved Bounds.**

Shiri Chechik (Tel-Aviv University)**Learning Mixtures of Gaussians in High Dimensions.**

Rong Ge (Microsoft Research New England); Qingqing Huang (MIT); Sham M. Kakade (Microsoft Research New England)**On the Lovasz Theta function for Independent Sets.**

Nikhil Bansal (TU Eindhoven), Anupam Gupta (CMU), Guru Guruganesh (CMU)**Secretary Problems with Non-Uniform Arrival Order.**

Thomas Kesselheim (Max-Planck-Institut fur Informatik); Robert Kleinberg (Cornell University and Microsoft Research); Rad Niazadeh (Cornell University)**Proof of the satisfiability conjecture for large k.**

Jian Ding (University of Chicago); Allan Sly (UC Berkeley and Australian National University); Nike Sun (Microsoft Research and MIT)**How Well Can Graphs Represent Wireless Interference?**

Magnus M. Halldorsson (Reykjavik University) and Tigran Tonoyan (Reykjavik University)**Tight bounds for learning a mixture of two Gaussians.**

Moritz Hardt (IBM Research Almaden); Eric Price (The University of Texas at Austin)**Succinct Randomized Encodings and their Applications.**

Nir Bitansky (MIT); Sanjam Garg (University of California, Berkeley); Huijia Lin (University of California, Santa Barbara); Rafael Pass (Cornell University); Sidharth Telang (Cornell University)**An Interactive Information Odometer and Applications.**

Mark Braverman (Princeton University) and Omri Weinstein (Princeton University)**Efficiently learning Ising models on Arbitrary Graphs.**

Guy Bresler (MIT)**Sum of Squares Lower Bounds from Pairwise Independence.**

Boaz Barak (Microsoft Research), Pravesh Kothari (University of Texas at Austin), Siu On Chan (Microsoft Research)**Consistency Thresholds for the Planted Bisection Model.**

Elchanan Mossel (U.C. Berkeley and University of Pennsylvania) ; Joe Neeman (U.T. Austin); Allan Sly (U.C. Berkeley and Australian National University)**Randomized Rounding for the Largest $j$-Simplex Problem.**

Aleksandar Nikolov (Microsoft Research)**Hardness of Graph Pricing Through Generalized Max-Dicut.**

Euiwoong Lee (Carnegie Mellon)**Adjacency labeling schemes and induced-universal graphs.**

Stephen Alstrup (University of Copenhagen), Haim Kaplan (Tel Aviv University), Mikkel Thorup (University of Copenhagen), Uri Zwick (Tel-Aviv University)**On the Complexity of Nash Equilibria in Anonymous Games.**

Xi Chen (Georgia Institute of Technology); David Durfee (Columbia University); Anthi Orfanou (Columbia University)**Analysis of a Classical Matrix Preconditioning Algorithm.**

Leonard J. Schulman (Caltech); Alistair Sinclair (UC Berkeley)**Online Submodular Welfare Maximization: Greedy beats 1/2.**

Nitish Korula (Google Research); Vahab Mirrokni (Google Research); Morteza Zadimoghaddam (Google Research)**Preserving Statistical Validity in Adaptive Data Analysis.**

Cynthia Dwork (Microsoft Research); Vitaly Feldman (IBM Research - Almaden); Moritz Hardt (IBM Research - Almaden); Toniann Pitassi (University of Toronto); Omer Reingold; Aaron Roth (University of Pennsylvania)**High Parallel Complexity Graphs and Memory-Hard Functions.**

Jo\"el Alwen (IST Austria); Vladimir Serbinenko (Google Z\"urich)**Almost Optimal Pseudorandom Generators for Spherical Caps.**

Pravesh K. Kothari (The University of Texas at Austin); Raghu Meka (University of California Los Angeles)**The communication complexity of interleaved group products.**

W. T. Gowers (University of Cambridge); Emanuele Viola (Northeastern & Harvard)**Leveled Fully Homomorphic Signatures from Standard Lattices.**

Sergey Gorbunov (MIT); Vinod Vaikuntanathan (MIT); Daniel Wichs (Northeastern)**Local, Private, Efficient Protocols for Succinct Histograms.**

Raef Bassily (The Pennsylvania State University); Adam Smith (The Pennsylvania State University)**Faster canonical forms for primitive coherent configurations.**

John Wilmes (University of Chicago) and Xiaorui Sun (Columbia University)**Approximating the Nash Social Welfare with Indivisible Items.**

Richard Cole (New York University) and Vasilis Gkatzelis (Stanford University)**Optimal Data-Dependent Hashing for Approximate Near Neighbors.**

Alexandr Andoni (Simons Institute) and Ilya Razenshteyn (MIT)**The List Decoding Radius of Reed Muller Codes over Small Fields.**

Abhishek Bhowmick (University of Texas at Austin) and Shachar Lovett (University of California, San Diego)**Time lower bounds for nonadaptive turnstile streaming algorithms.**

Kasper Green Larsen (Aarhus University), Jelani Nelson (Harvard University), Huy Le Nguyen (Simons Institute)**Lower bounds on the size of semidefinite programming relaxations.**

James R. Lee (University of Washington), Prasad Raghavendra (UC Berkeley), David Steurer (Cornell)**Bypassing KLS: Gaussian Cooling and an $O*(n^3)$ Volume Algorithm.**

Ben Cousins (Georgia Tech); Santosh Vempala (Georgia Tech)**Learning Arbitrary Statistical Mixtures of Discrete Distributions.**

Jian Li (Tsinghua University), Yuval Rabani (The Hebrew University), Leonard J. Schulman (California Institute of Technology), Chaitanya Swamy (University of Waterloo)**Nearly-Linear Time Positive LP Solver with Faster Convergence Rate.**

Zeyuan Allen-Zhu (MIT); Lorenzo Orecchia (Boston University)**Inapproximability of combinatorial problems via small LPs and SDPs.**

Gábor Braun (Georgia Tech); Sebastian Pokutta (Georgia Tech); Daniel Zink (Georgia Tech)**Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms.**

Anand Louis (Princeton University)**A characterization of the capacity of online (causal) binary channels.**

Zitan Chen (The Chinese University of Hong Kong), Sidharth Jaggi (The Chinese University of Hong Kong), Michael Langberg (SUNY at Buffalo)**A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection.**

Kyle Fox (Duke University); Philip N. Klein (Brown University); Shay Mozes (Interdisciplinary Center, Herzliya, Israel)**Fast Matrix Multiplication: Limitations of Coppersmith-Winograd Method.**

Andris Ambainis (University of Latvia); Yuval Filmus (Institute for Advanced Study); François Le Gall (University of Tokyo)**Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time.**

Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo, Japan) and Mikkel Thorup (University of Copenhagen, Denmark)**Randomized Composable Core-sets for Distributed Submodular Maximization.**

Vahab Mirrokni (Google Research New York); Morteza Zadimoghaddam (Google Research New York)**Succinct Garbling and Indistinguishability Obfuscation for RAM Programs.**

Ran Canetti (Tel-Aviv University and Boston University); Justin Holmgren (MIT); Abhishek Jain (Johns Hopkins); Vinod Vaikuntanathan (MIT)**Matching triangles and basing hardness on an extremely popular conjecture.**

Amir Abboud (Stanford), Virginia Vassilevska Williams (Stanford), Huacheng Yu (Stanford)**Beyond the Euler characteristic: Approximating the genus of general graphs.**

Ken-ichi Kawarabayashi (National Institute of Informatics, Japan); ; Anastasios Sidiropoulos (The Ohio State University)**On the Complexity of Random Satisfiability Problems with Planted Solutions.**

Vitaly Feldman (IBM Research - Almaden); Will Perkins (University of Birmingham); Santosh Vempala (Georgia Tech)**Dimensionality Reduction for k-Means Clustering and Low Rank Approximation.**

Michael B. Cohen (MIT); Sam Elder (MIT); Cameron Musco (MIT); Christopher Musco (MIT); Madalina Persu (MIT)**Indistinguishability Obfuscation for Turing Machines with Unbounded Memory.**

Venkata Koppula (University of Texas at Austin); Allison B. Lewko (Columbia University); Brent Waters (University of Texas at Austin)**Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method.**

Boaz Barak (Microsoft Research); Jonathan Kelner (MIT); David Steurer (Cornell University)**Exponential Separation of Information and Communication for Boolean Functions.**

Anat Ganor (Weizmann Institute); Gillat Kol (IAS); Ran Raz (Weizmann Institute & IAS)**Toward a unified theory of sparse dimensionality reduction in Euclidean space.**

Jean Bourgain (IAS), Sjoerd Dirksen (RWTH Aachen University), Jelani Nelson (Harvard)**Solving the Shortest Vector Problem in 2^n time via Discrete Gaussian Sampling.**

Divesh Aggarwal (École polytechnique fédérale de Lausanne); Daniel Dadush (Centrum Wiskunde & Informatica); Oded Regev (New York University); Noah Stephens-Davidowitz (New York University)**An improved version of the Random-Facet pivoting rule for the simplex algorithm.**

Thomas Dueholm Hansen (Stanford University); Uri Zwick (Tel Aviv University)**Forrelation: A Problem that Optimally Separates Quantum from Classical Computing.**

Scott Aaronson (MIT) and Andris Ambainis (University of Latvia)**Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension.**

Amit Daniely (Hebrew University), Michael Schapira (Hebrew University), Gal Shahaf (Hebrew University)**Polynomially low error PCPs with $\poly\loglog\n$ queries via modular composition.**

Irit Dinur (Weizman Institute); Prahladh Harsha (TIFR); Guy Kindler (Hebrew University)**Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates.**

Zeyuan Allen-Zhu (MIT); Zhenyu Liao (Boston University); Lorenzo Orecchia (Boston University)**Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices.**

Ankur Moitra (MIT)**Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false).**

Arturs Backurs (MIT) and Piotr Indyk (MIT)**Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries.**

Xi Chen (Columbia University); Anindya De (IAS/DIMACS); Rocco A. Servedio (Columbia University); Li-Yang Tan (Columbia University/Simons Institute)**The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree.**

Jakub Lacki (University of Warsaw), Jakub Ocwieja (University of Warsaw), Marcin Pilipczuk (University of Warwick and Unviersity of Warsaw), Piotr Sankowski (Univerisity of Warsaw), Anna Zych (University of Warsaw)**A directed isoperimetric inequality with application to Bregman near neighbor lower bounds.**

Amirali Abdullah (University of Utah), Suresh Venkatasubramanian (University of Utah)**Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity.**

Ittai Abraham (VMware Research); Danny Dolev (Hebrew University)**Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions.**

Shachar Lovett (University of California, San Diego); Jiapeng Zhang (University of California, San Diego)**Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.**

Sayan Bhattacharya (The Institute of Mathematical Sciences, Chennai, India), Monika Henzinger (University of Vienna), Danupon Nanongkai (KTH Royal Institute of Technology), Charalampos E. Tsourakakis (Harvard University)**Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs.**

Shuchi Chawla (University of Wisconsin-Madison); Konstantin Makarychev (Microsoft Research); Tselil Schramm (UC Berkeley); Grigory Yaroslavtsev (University of Pennsylvania)**Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.**

Monika Henzinger (University of Vienna, Austria); Sebastian Krinninger (University of Vienna, Austria); Danupon Nanongkai (KTH Royal Institute of Technology); Thatchaphol Saranurak (KTH Royal Institute of Technology)**Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem.**

Siddharth Barma (California Institute of Technology)**A New, Fully Quantum Notion of Information Complexity, and an Application to Direct Sum for Bounded Round Quantum Communication Complexity.**

Dave Touchette (Université de Montréal)