| 2019 | "Quantum Supremacy" and the Complexity of Random Circuit Sampling. Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani |
| 2019 | A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates. Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan |
| 2019 | A Log-Sobolev Inequality for the Multislice, with Applications. Yuval Filmus, Ryan O'Donnell, Xinyu Wu |
| 2019 | A New Approach to Multi-Party Peer-to-Peer Communication Complexity. Adi Rosén, Florent Urrutia |
| 2019 | A Note on the Quantum Query Complexity of Permutation Symmetric Functions. André Chailloux |
| 2019 | A Schur Complement Cheeger Inequality. Aaron Schild |
| 2019 | A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. Sepehr Assadi, Michael Kapralov, Sanjeev Khanna |
| 2019 | Adaptive Boolean Monotonicity Testing in Total Influence Time. Deeparnab Chakrabarty, C. Seshadhri |
| 2019 | Adventures in Monotone Complexity and TFNP. Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov |
| 2019 | Adversarially Robust Property-Preserving Hash Functions. Elette Boyle, Rio LaVigne, Vinod Vaikuntanathan |
| 2019 | Alea Iacta Est: Auctions, Persuasion, Interim Rules, and Dice. Shaddin Dughmi, David Kempe, Ruixin Qiang |
| 2019 | Algorithmic Polarization for Hidden Markov Models. Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan |
| 2019 | Algorithms, Bounds, and Strategies for Entangled XOR Games. Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, Anand Natarajan |
| 2019 | Almost Envy-Free Allocations with Connected Bundles. Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, William S. Zwicker |
| 2019 | Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't. Yan Jin, Elchanan Mossel, Govind Ramnarayan |
| 2019 | Bitcoin: A Natural Oligopoly. Nick Arnosti, S. Matthew Weinberg |
| 2019 | Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity. Wei Chen, Shang-Hua Teng, Hanrui Zhang |
| 2019 | Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols. Lijie Chen, Ruosong Wang |
| 2019 | Cubic Formula Size Lower Bounds Based on Compositions with Majority. Anna Gál, Avishay Tal, Adrian Trejo Nuñez |
| 2019 | Density Estimation for Shift-Invariant Multidimensional Distributions. Anindya De, Philip M. Long, Rocco A. Servedio |
| 2019 | Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times. Klaus Jansen, Kim-Manuel Klein, Marten Maack, Malin Rau |
| 2019 | Erasures vs. Errors in Local Decoding and Property Testing. Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma |
| 2019 | Every Set in P Is Strongly Testable Under a Suitable Encoding. Irit Dinur, Oded Goldreich, Tom Gur |
| 2019 | Expander-Based Cryptography Meets Natural Proofs. Igor Carboni Oliveira, Rahul Santhanam, Roei Tell |
| 2019 | Fairness Under Composition. Cynthia Dwork, Christina Ilvento |
| 2019 | Fisher Zeros and Correlation Decay in the Ising Model. Jingcheng Liu, Alistair Sinclair, Piyush Srivastava |
| 2019 | From Local to Robust Testing via Agreement Testing. Irit Dinur, Prahladh Harsha, Tali Kaufman, Noga Ron-Zewi |
| 2019 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2019 | Game Efficiency Through Linear Programming Duality. Kim Thang Nguyen |
| 2019 | Hamiltonian Sparsification and Gap-Simulation. Dorit Aharonov, Leo Zhou |
| 2019 | How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts. Thibaut Horel, Sunoo Park, Silas Richelson, Vinod Vaikuntanathan |
| 2019 | Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization. Constantinos Daskalakis, Ioannis Panageas |
| 2019 | Learning Time Dependent Choice. Zachary Chase, Siddharth Prasad |
| 2019 | Local Computation Algorithms for Spanners. Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee |
| 2019 | Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. Amit Levi, Erik Waingarten |
| 2019 | On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. Karthik C. S., Pasin Manurangsi |
| 2019 | On Integer Programming and Convolution. Klaus Jansen, Lars Rohwedder |
| 2019 | On Locality-Sensitive Orderings and Their Applications. Timothy M. Chan, Sariel Har-Peled, Mitchell Jones |
| 2019 | On Solving Linear Systems in Sublinear Time. Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow |
| 2019 | On the Algorithmic Power of Spiking Neural Networks. Chi-Ning Chou, Kai-Min Chung, Chi-Jen Lu |
| 2019 | On the Communication Complexity of High-Dimensional Permutations. Nati Linial, Toniann Pitassi, Adi Shraibman |
| 2019 | On the Communication Complexity of Key-Agreement Protocols. Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff |
| 2019 | On the Complexity of Symmetric Polynomials. Markus Bläser, Gorav Jindal |
| 2019 | Placing Conditional Disclosure of Secrets in the Communication Complexity Universe. Benny Applebaum, Prashant Nalini Vasudevan |
| 2019 | Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing. Alessandro Chiesa, Peter Manohar, Igor Shinkar |
| 2019 | Proofs of Catalytic Space. Krzysztof Pietrzak |
| 2019 | Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal |
| 2019 | Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle. Dylan M. McKay, Richard Ryan Williams |
| 2019 | Random Projection in the Brain and Computation with Assemblies of Neurons. Christos H. Papadimitriou, Santosh S. Vempala |
| 2019 | SOS Lower Bounds with Hard Constraints: Think Global, Act Local. Pravesh K. Kothari, Ryan O'Donnell, Tselil Schramm |
| 2019 | Secret Sharing with Binary Shares. Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang |
| 2019 | Semi-Online Bipartite Matching. Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, Erik Vee |
| 2019 | Simple Verifiable Delay Functions. Krzysztof Pietrzak |
| 2019 | Simulating Random Walks on Graphs in the Streaming Model. Ce Jin |
| 2019 | Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. Boaz Barak, Pravesh K. Kothari, David Steurer |
| 2019 | Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs. Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, Avi Wigderson |
| 2019 | Strategies for Quantum Races. Troy Lee, Maharshi Ray, Miklos Santha |
| 2019 | Submodular Secretary Problem with Shortlists. Shipra Agrawal, Mohammad Shadravan, Cliff Stein |
| 2019 | Sum of Squares Lower Bounds from Symmetry and a Good Story. Aaron Potechin |
| 2019 | Tensor Network Complexity of Multilinear Maps. Per Austrin, Petteri Kaski, Kaie Kubjas |
| 2019 | Testing Local Properties of Arrays. Omri Ben-Eliezer |
| 2019 | The Complexity of User Retention. Eli Ben-Sasson, Eden Saig |
| 2019 | The Orthogonal Vectors Conjecture for Branching Programs and Formulas. Daniel M. Kane, Richard Ryan Williams |
| 2019 | The Paulsen Problem Made Simple. Linus Hamilton, Ankur Moitra |
| 2019 | The Space Complexity of Mirror Games. Sumegha Garg, Jon Schneider |
| 2019 | The Subgraph Testing Model. Oded Goldreich, Dana Ron |
| 2019 | Torus Polynomials: An Algebraic Approach to ACC Lower Bounds. Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao |
| 2018 | 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, San Diego, California, USA, January 10-12, 2019 Avrim Blum |