| 2023 | 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, MIT, Cambridge, Massachusetts, USA, January 10-13, 2023 Yael Tauman Kalai |
| 2023 | A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems. Monika Henzinger, Billy Jin, Richard Peng, David P. Williamson |
| 2023 | A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators. Idan Attias, Edith Cohen, Moshe Shechner, Uri Stemmer |
| 2023 | A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems. Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, Zihan Tan |
| 2023 | A Subpolynomial-Time Algorithm for the Free Energy of One-Dimensional Quantum Systems in the Thermodynamic Limit. Hamza Fawzi, Omar Fawzi, Samuel O. Scalet |
| 2023 | Algorithms with More Granular Differential Privacy Guarantees. Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thomas Steinke |
| 2023 | All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method. Sepehr Assadi, Aaron Bernstein, Zachary Langley |
| 2023 | An Algorithmic Bridge Between Hamming and Levenshtein Distances. Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha |
| 2023 | An Improved Lower Bound for Matroid Intersection Prophet Inequalities. Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg |
| 2023 | Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks. Antoine El-Hayek, Monika Henzinger, Stefan Schmid |
| 2023 | Asynchronous Multi-Party Quantum Computation. Vipul Goyal, Chen-Da Liu-Zhang, Justin Raizes, João Ribeiro |
| 2023 | Beeping Shortest Paths via Hypergraph Bipartite Decomposition. Fabien Dufoulon, Yuval Emek, Ran Gelles |
| 2023 | Beyond Worst-Case Budget-Feasible Mechanism Design. Aviad Rubinstein, Junyao Zhao |
| 2023 | Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization. Papri Dey, Ravi Kannan, Nick Ryder, Nikhil Srivastava |
| 2023 | Black-Box Constructive Proofs Are Unavoidable. Lijie Chen, Ryan Williams, Tianqi Yang |
| 2023 | Bootstrapping Homomorphic Encryption via Functional Encryption. Nir Bitansky, Tomer Solomon |
| 2023 | Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, Aleksandrs Slivkins |
| 2023 | Certificate Games. Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny |
| 2023 | Certification with an NP Oracle. Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan |
| 2023 | Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly. Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Huacheng Yu |
| 2023 | Clustering Permutations: New Techniques with Streaming Applications. Diptarka Chakraborty, Debarati Das, Robert Krauthgamer |
| 2023 | Communication Complexity of Inner Product in Symmetric Normed Spaces. Alexandr Andoni, Jaroslaw Blasiok, Arnold Filtser |
| 2023 | Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes. Lunjia Hu, Charlotte Peale |
| 2023 | Concentration Bounds for Quantum States and Limitations on the QAOA from Polynomial Approximations. Anurag Anshu, Tony Metger |
| 2023 | Consensus Division in an Arbitrary Ratio. Paul Goldberg, Jiawei Li |
| 2023 | Constant-Depth Sorting Networks. Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii |
| 2023 | Counting Subgraphs in Somewhere Dense Graphs. Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, Marc Roth |
| 2023 | Decision-Making Under Miscalibration. Guy N. Rothblum, Gal Yona |
| 2023 | Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More. Qipeng Liu |
| 2023 | Differentially Private Continual Releases of Streaming Frequency Moment Estimations. Alessandro Epasto, Jieming Mao, Andres Muñoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, Peilin Zhong |
| 2023 | Downward Self-Reducibility in TFNP. Prahladh Harsha, Daniel Mitropolsky, Alon Rosen |
| 2023 | Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices. Prayaag Venkat |
| 2023 | Efficiently Testable Circuits. Mirza Ahad Baig, Suvradip Chakraborty, Stefan Dziembowski, Malgorzata Galazka, Tomasz Lizurej, Krzysztof Pietrzak |
| 2023 | Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free. Greg Bodwin, Michael Dinitz, Yasamin Nazari |
| 2023 | Exact Completeness of LP Hierarchies for Linear Codes. Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones |
| 2023 | Expander Decomposition in Dynamic Streams. Arnold Filtser, Michael Kapralov, Mikhail Makarov |
| 2023 | Exponential Separations Using Guarded Extension Variables. Emre Yolcu, Marijn J. H. Heule |
| 2023 | Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP. Amol Pasarkar, Christos H. Papadimitriou, Mihalis Yannakakis |
| 2023 | False Consensus, Information Theory, and Prediction Markets. Yuqing Kong, Grant Schoenebeck |
| 2023 | Fractional Certificates for Bounded Functions. Shachar Lovett, Jiapeng Zhang |
| 2023 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2023 | Garland's Technique for Posets and High Dimensional Grassmannian Expanders. Tali Kaufman, Ran J. Tessler |
| 2023 | Generalized Private Selection and Testing with High Confidence. Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer |
| 2023 | Graph Searching with Predictions. Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, Zhouzi Li |
| 2023 | HappyMap : A Generalized Multicalibration Method. Zhun Deng, Cynthia Dwork, Linjun Zhang |
| 2023 | Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique. Pasin Manurangsi |
| 2023 | Improved Monotonicity Testers via Hypercube Embeddings. Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer |
| 2023 | Incompressiblity and Next-Block Pseudoentropy. Iftach Haitner, Noam Mazor, Jad Silbak |
| 2023 | Is It Easier to Count Communities Than Find Them? Cynthia Rush, Fiona Skerman, Alexander S. Wein, Dana Yang |
| 2023 | Is This Correct? Let's Check! Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, Madhu Sudan |
| 2023 | Is Untrusted Randomness Helpful? Uma Girish, Ran Raz, Wei Zhan |
| 2023 | Karchmer-Wigderson Games for Hazard-Free Computation. Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh |
| 2023 | Kolmogorov Complexity Characterizes Statistical Zero Knowledge. Eric Allender, Shuichi Hirahara, Harsha Tirumala |
| 2023 | Learning Reserve Prices in Second-Price Auctions. Yaonan Jin, Pinyan Lu, Tao Xiao |
| 2023 | Learning Versus Pseudorandom Generators in Constant Parallel Time. Shuichi Hirahara, Mikito Nanashima |
| 2023 | Lifting to Parity Decision Trees via Stifling. Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif |
| 2023 | List Agreement Expansion from Coboundary Expansion. Roy Gotlib, Tali Kaufman |
| 2023 | Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments. Varun Gupta, Ravishankar Krishnaswamy, Sai Sandeep, Janani Sundaresan |
| 2023 | Loss Minimization Through the Lens Of Outcome Indistinguishability. Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, Udi Wieder |
| 2023 | Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom. Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang |
| 2023 | Making Auctions Robust to Aftermarkets. Moshe Babaioff, Nicole Immorlica, Yingkai Li, Brendan Lucier |
| 2023 | Making Decisions Under Outcome Performativity. Michael P. Kim, Juan C. Perdomo |
| 2023 | Matrix Multiplication via Matrix Groups. Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans |
| 2023 | Matroid Partition Property and the Secretary Problem. Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
| 2023 | Necessary Conditions in Multi-Server Differential Privacy. Albert Cheu, Chao Yan |
| 2023 | New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method. Lijie Chen |
| 2023 | Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds. Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena |
| 2023 | On Computing Homological Hitting Sets. Ulrich Bauer, Abhishek Rathod, Meirav Zehavi |
| 2023 | On Disperser/Lifting Properties of the Index and Inner-Product Functions. Paul Beame, Sajin Koroth |
| 2023 | On Flipping the Fréchet Distance. Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk |
| 2023 | On Identity Testing and Noncommutative Rank Computation over the Free Skew Field. Vikraman Arvind, Abhranil Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, C. Ramya |
| 2023 | On Interactive Proofs of Proximity with Proof-Oblivious Queries. Oded Goldreich, Guy N. Rothblum, Tal Skverer |
| 2023 | On Low-End Obfuscation and Learning. Elette Boyle, Yuval Ishai, Pierre Meyer, Robert Robere, Gal Yehuda |
| 2023 | On Oracles and Algorithmic Methods for Proving Lower Bounds. Nikhil Vyas, Ryan Williams |
| 2023 | On the Computational Hardness Needed for Quantum Cryptography. Zvika Brakerski, Ran Canetti, Luowen Qian |
| 2023 | Online Learning and Bandits with Queried Hints. Aditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, Kamesh Munagala |
| 2023 | Online Pen Testing. Mingda Qiao, Gregory Valiant |
| 2023 | Opponent Indifference in Rating Systems: A Theoretical Case for Sonas. Greg Bodwin, Forest Zhang |
| 2023 | PPP-Completeness and Extremal Combinatorics. Romain Bourneuf, Lukás Folwarczný, Pavel Hubácek, Alon Rosen, Nikolaj I. Schwartzbach |
| 2023 | Private Counting of Distinct and k-Occurring Items in Time Windows. Badih Ghazi, Ravi Kumar, Jelani Nelson, Pasin Manurangsi |
| 2023 | Proofs of Quantumness from Trapdoor Permutations. Tomoyuki Morimae, Takashi Yamakawa |
| 2023 | Quantum Algorithms and the Power of Forgetting. Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani |
| 2023 | Quantum Majority Vote. Harry Buhrman, Noah Linden, Laura Mancinska, Ashley Montanaro, Maris Ozols |
| 2023 | Quantum Proofs of Deletion for Learning with Errors. Alexander Poremba |
| 2023 | Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover Interactive Proofs into Unentanglement. Sevag Gharibian, Dorian Rudolph |
| 2023 | Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses. Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi |
| 2023 | Recovery from Non-Decomposable Distance Oracles. Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang |
| 2023 | Resilience of 3-Majority Dynamics to Non-Uniform Schedulers. Uri Meir, Rotem Oshman, Ofer Shayevitz, Yuval Volkov |
| 2023 | Rigidity for Monogamy-Of-Entanglement Games. Anne Broadbent, Eric Culf |
| 2023 | Rigidity in Mechanism Design and Its Applications. Shahar Dobzinski, Ariel Shaulker |
| 2023 | Rounding via Low Dimensional Embeddings. Mark Braverman, Dor Minzer |
| 2023 | Secure Distributed Network Optimization Against Eavesdroppers. Yael Hitron, Merav Parter, Eylon Yogev |
| 2023 | Strategyproof Scheduling with Predictions. Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan |
| 2023 | Symmetric Formulas for Products of Permutations. William He, Benjamin Rossman |
| 2023 | TFNP Characterizations of Proof Systems and Monotone Circuits. Sam Buss, Noah Fleming, Russell Impagliazzo |
| 2023 | The Complexity of Infinite-Horizon General-Sum Stochastic Games. Yujia Jin, Vidya Muthukumar, Aaron Sidford |
| 2023 | The Strength of Equality Oracles in Communication. Toniann Pitassi, Morgan Shirley, Adi Shraibman |
| 2023 | The Time Complexity of Consensus Under Oblivious Message Adversaries. Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid, Ulrich Schmid |
| 2023 | Unitary Property Testing Lower Bounds by Polynomials. Adrian She, Henry Yuen |
| 2023 | Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm. Fabrizio Grandoni, Claire Mathieu, Hang Zhou |
| 2023 | Vertex Sparsification for Edge Connectivity in Polynomial Time. Yang P. Liu |
| 2023 | What Can Cryptography Do for Decentralized Mechanism Design? Elaine Shi, Hao Chung, Ke Wu |
| 2023 | Worst-Case to Expander-Case Reductions. Amir Abboud, Nathan Wallheimer |