| 2018 | 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, Cambridge, MA, USA, January 11-14, 2018 Anna R. Karlin |
| 2018 | A Candidate for a Strong Separation of Information and Communication. Mark Braverman, Anat Ganor, Gillat Kol, Ran Raz |
| 2018 | A Complete Characterization of Unitary Quantum Space. Bill Fefferman, Cedric Yen-Yu Lin |
| 2018 | A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory. Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, Michael Kowalczyk |
| 2018 | A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma. Greg Yang |
| 2018 | A Local-Search Algorithm for Steiner Forest. Martin Groß, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt, José Verschae |
| 2018 | A Quasi-Random Approach to Matrix Spectral Analysis. Michael Ben-Or, Lior Eldar |
| 2018 | Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method. Jelena Diakonikolas, Lorenzo Orecchia |
| 2018 | Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory. Peter Bürgisser, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson |
| 2018 | An Axiomatic Study of Scoring Rule Markets. Rafael M. Frongillo, Bo Waggoner |
| 2018 | Approximate Clustering with Same-Cluster Queries. Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal, Amit Kumar |
| 2018 | Barriers for Rank Methods in Arithmetic Complexity. Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson |
| 2018 | Competing Bandits: Learning Under Competition. Yishay Mansour, Aleksandrs Slivkins, Zhiwei Steven Wu |
| 2018 | Computing Exact Minimum Cuts Without Knowing the Graph. Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg |
| 2018 | Convergence Results for Neural Networks via Electrodynamics. Rina Panigrahy, Ali Rahimi, Sushant Sachdeva, Qiuyi Zhang |
| 2018 | Differential Privacy on Finite Computers. Victor Balcer, Salil P. Vadhan |
| 2018 | Distance-Preserving Graph Contractions. Aaron Bernstein, Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, Frieder Smolny |
| 2018 | ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. Irit Dinur, Pasin Manurangsi |
| 2018 | Edge Estimation with Independent Set Oracles. Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha |
| 2018 | Efficient Testing without Efficient Regularity. Lior Gishboliner, Asaf Shapira |
| 2018 | Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning. Dana Moshkovitz, Michal Moshkovitz |
| 2018 | Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity. Yuqing Kong, Grant Schoenebeck |
| 2018 | Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. Amir Abboud, Aviad Rubinstein |
| 2018 | Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy. Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, Virginia Vassilevska Williams |
| 2018 | Finite Sample Differentially Private Confidence Intervals. Vishesh Karwa, Salil P. Vadhan |
| 2018 | Foundations of Homomorphic Secret Sharing. Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin, Stefano Tessaro |
| 2018 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2018 | Further Limitations of the Known Approaches for Matrix Multiplication. Josh Alman, Virginia Vassilevska Williams |
| 2018 | Graph Clustering using Effective Resistance. Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis Gharan |
| 2018 | Improper Learning by Refuting. Pravesh K. Kothari, Roi Livni |
| 2018 | Information Value of Two-Prover Games. Mark Braverman, Young Kun-Ko |
| 2018 | Lattice-based Locality Sensitive Hashing is Optimal. Karthekeyan Chandrasekaran, Daniel Dadush, Venkata Gandikota, Elena Grigorescu |
| 2018 | Learning Discrete Distributions from Untrusted Batches. Mingda Qiao, Gregory Valiant |
| 2018 | Learning Dynamics and the Co-Evolution of Competing Sexual Species. Georgios Piliouras, Leonard J. Schulman |
| 2018 | Limits for Rumor Spreading in Stochastic Populations. Lucas Boczkowski, Ofer Feinerman, Amos Korman, Emanuele Natale |
| 2018 | Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs. Shay Solomon |
| 2018 | Local Decoding and Testing of Polynomials over Grids. Srikanth Srinivasan, Madhu Sudan |
| 2018 | Long Term Memory and the Densest K-Subgraph Problem. Robert Legenstein, Wolfgang Maass, Christos H. Papadimitriou, Santosh S. Vempala |
| 2018 | Making Asynchronous Distributed Computations Robust to Channel Noise. Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler |
| 2018 | Matrix Completion and Related Problems via Strong Duality. Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, Hongyang Zhang |
| 2018 | Minimum Circuit Size, Graph Isomorphism, and Related Problems. Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan |
| 2018 | Non-Negative Sparse Regression and Column Subset Selection with L1 Error. Aditya Bhaskara, Silvio Lattanzi |
| 2018 | On Price versus Quality. Avrim Blum, Yishay Mansour |
| 2018 | Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case. Yuqing Kong, Grant Schoenebeck |
| 2018 | Proofs of Proximity for Distribution Testing. Alessandro Chiesa, Tom Gur |
| 2018 | Pseudo-Deterministic Proofs. Shafi Goldwasser, Ofer Grossman, Dhiraj Holden |
| 2018 | Pseudorandom Generators for Low Sensitivity Functions. Pooya Hatami, Avishay Tal |
| 2018 | Quantum Query Algorithms are Completely Bounded Forms. Srinivasan Arunachalam, Jop Briët, Carlos Palazuelos |
| 2018 | Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity. Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh, Meirav Zehavi |
| 2018 | Recovering Structured Probability Matrices. Qingqing Huang, Sham M. Kakade, Weihao Kong, Gregory Valiant |
| 2018 | Relaxed Locally Correctable Codes. Tom Gur, Govind Ramnarayan, Ron D. Rothblum |
| 2018 | Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. Jacob Steinhardt, Moses Charikar, Gregory Valiant |
| 2018 | Scheduling with Explorable Uncertainty. Christoph Dürr, Thomas Erlebach, Nicole Megow, Julie Meißner |
| 2018 | Selection Problems in the Presence of Implicit Bias. Jon M. Kleinberg, Manish Raghavan |
| 2018 | Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets. Oded Goldreich, Guy N. Rothblum |
| 2018 | Size, Cost and Capacity: A Semantic Technique for Hard Random QBFs. Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde |
| 2018 | Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff |
| 2018 | Stabbing Planes. Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere |
| 2018 | Toward a Theory of Markov Influence Systems and their Renormalization. Bernard Chazelle |
| 2018 | Towards a Unified Complexity Theory of Total Functions. Paul W. Goldberg, Christos H. Papadimitriou |
| 2018 | Zero-Knowledge Proofs of Proximity. Itay Berman, Ron D. Rothblum, Vinod Vaikuntanathan |