ITCS 2023 Accepted Papers

  1. Rigidity for Monogamy-of-Entanglement Games

    Authors: Anne Broadbent, Eric Culf (University of Ottawa)

  2. Opponent Indifference in Rating Systems: A Theoretical Case for Sonas

    Authors: Greg Bodwin, Forest Zhang (University of Michigan)

  3. Online Learning and Bandits with Queried Hints

    Authors: Aditya Bhaskara (University of Utah); Sreenivas Gollapudi (Google); Sungjin Im (University of California-Merced); Kostas Kollias (Google); Kamesh Munagala (Duke University)

  4. Improved Monotonicity Testing Over the Hypergrid via Hypercube Embedddings

    Authors: Mark Braverman (Princeton University); Subhash Khot (NYU); Guy Kindler (Hebrew University of Jerusalem); Dor Minzer (MIT)

  5. Learning Reserve Prices in Second-Price Auctions

    Authors: Yaonan Jin (Columbia University); Pinyan Lu (Shanghai University of Finance and Economics); Tao Xiao (Huawei TCS Lab)

  6. Symmetric Formulas for Products of Permutations

    Authors: William He, Benjamin Rossman (Duke University)

  7. Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks

    Authors: Antoine El-Hayek, Monika Henzinger (University of Vienna); Stefan Schmid (University of Vienna & TU Berlin)

  8. A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems

    Authors: Monika Henzinger (University of Vienna); Billy Jin (Cornell University); Richard Peng (Carnegie Mellon University and University of Waterloo); David Williamson (Cornell University)

  9. Strategyproof Scheduling with Predictions

    Authors: Eric Balkanski (Columbia University); Vasilis Gkatzelis, Xizhi Tan (Drexel University)

  10. Learning versus Pseudorandom Generators in Constant Parallel Time

    Authors: Shuichi Hirahara (National Institute of Informatics); Mikito Nanashima (Tokyo Institute of Technology)

  11. Exact Completeness of LP Hierarchies for Linear Codes

    Authors: Leonardo Nagami Coregliano, Fernando Granha Jeronimo (Institute for Advanced Study); Chris Jones (University of Chicago)

  12. Proofs of Quantumness from Trapdoor Permutations

    Authors: Tomoyuki Morimae (Kyoto University); Takashi Yamakawa (NTT Social Informatics Laboratories)

  13. Exponential separations using guarded extension variables

    Authors: Emre Yolcu, Marijn Heule (Carnegie Mellon University)

  14. Quantum algorithms and the power of forgetting

    Authors: Amin Shiraz Gilani, Andrew M. Childs, Matthew Coudron (University of Maryland)

  15. On Interactive Proofs of Proximity with Proof-Oblivious Queries

    Authors: Oded Goldreich (Weizmann Institute of Science); Guy N. Rothblum (Apple); Tal Skverer (Weizmann Institute of Science)

  16. Matrix multiplication via matrix groups

    Authors: Jonah Blasiak (Department of Mathematics, Drexel University); Henry Cohn (Microsoft Research New England); Joshua A. Grochow (Departments of Computer Science and Mathematics, University of Colorado Boulder); Kevin Pratt (School of Computer Science, Carnegie Mellon University); Chris Umans (Department of Computing and Mathematical Sciences, California Institute of Technology)

  17. A New Conjecture on Hardness of Low-Degree 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems

    Authors: Julia Chuzhoy (Toyota Technological Institute at Chicago); Mina Dalirrooyfard (MIT); Vadim Grinberg (Weizmann Institute of Science); Zihan Tan (Rutgers University)

  18. Making Decisions under Outcome Performativity

    Authors: Michael P. Kim, Juan C. Perdomo (UC Berkeley)

  19. Loss Minimization through the lens of Outcome Indistinguishability

    Authors: Parikshit Gopalan (Apple); Lunjia Hu (Stanford University); Michael P. Kim (UC Berkeley); Omer Reingold (Stanford University); Udi Wieder (VMware)

  20. The Time Complexity of Consensus Under Oblivious Message Adversaries

    Authors: Hugo Rincon Galeana (Technische Universität Wien); Ami Paz (LISN - CNRS and Paris-Saclay University); Stefan Schmid (TU Berlin & Fraunhofer SIT); Ulrich Schmid (TU Wien); Kyrill Winkler (ITK Engineering, Vienna, Austria)

  21. Necessary Conditions in Multi-Server Differential Privacy

    Authors: Albert Cheu, Chao Yan (Georgetown University)

  22. On Oracles and Algorithmic Methods for Proving Lower Bounds

    Authors: Nikhil Vyas, Ryan Williams (MIT)

  23. Beyond Worst-Case Budget-Feasible Mechanism Design

    Authors: Aviad Rubinstein, Junyao Zhao (Stanford University)

  24. Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement

    Authors: Dorian Rudolph, Sevag Gharibian (Universität Paderborn)

  25. Unitary property testing lower bounds by polynomials

    Authors: Adrian She (University of Toronto); Henry Yuen (Columbia University)

  26. Incompressiblity and Next-Block Pseudoentropy

    Authors: Iftach Haitner, Noam Mazor, Jad Silbak (Tel Aviv University)

  27. PPP-Completeness and Extremal Combinatorics

    Authors: Romain Bourneuf (ENS de Lyon); Lukáš Folwarczný, Pavel Hubáček (Charles University); Alon Rosen (Bocconi University and Reichman University); Nikolaj Ignatieff Schwartzbach (Aarhus University)

  28. Beeping Shortest Paths via Hypergraph Bipartite Decomposition

    Authors: Fabien Dufoulon (University of Houston); Yuval Emek (Technion); Ran Gelles (Bar-Ilan University)

  29. Expander Decomposition in Dynamic Streams

    Authors: Arnold Filtser (Bar-Ilan University); Michael Kapralov, Mikhail Makarov (EPFL)

  30. Fractional certificates for bounded functions

    Authors: Shachar Lovett (University of California San Diego); Jiapeng Zhang (University of Southern California)

  31. Extremal Combinatorics, iterated pigeonhole arguments, and generalizations of PPP

    Authors: Amol Pasarkar, Christos Papadimitriou, Mihalis Yannakakis (Columbia University)

  32. Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More

    Authors: Qipeng Liu (Simons Institute)

  33. Kolmogorov Complexity Characterizes Statistical Zero Knowledge

    Authors: Eric Allender (Rutgers University); Shuichi Hirahara (National Institute of Informatics); Harsha Tirumala (Rutgers University)

  34. Vertex Sparsification for Edge Connectivity in Polynomial Time

    Authors: Yang P. Liu (Stanford University)

  35. On the computational hardness needed for quantum cryptography

    Authors: Zvika Brakerski (Weizmann Institute of Science); Ran Canetti, Luowen Qian (Boston University)

  36. Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses

    Authors: Chris Jones, Kunal Marwaha (University of Chicago); Juspreet Singh Sandhu (Harvard University); Jonathan Shi (Bocconi University)

  37. Rounding via Low Dimensional Embeddings

    Authors: Mark Braverman (Princeton University); Dor Minzer (MIT)

  38. Certification with an NP Oracle

    Authors: Guy Blanc, Caleb Koch (Stanford University); Jane Lange (MIT); Carmen Strassle, Li-Yang Tan (Stanford University)

  39. Unsplittable Euclidean Capacitated Vehicle Routing: A $(2+\epsilon)$-Approximation Algorithm

    Authors: Fabrizio Grandoni (IDSIA, University of Lugano); Claire Mathieu (École normale supérieure and CNRS); Hang Zhou (École Polytechnique)

  40. Efficient algorithms for certifying lower bounds on the discrepancy of random matrices

    Authors: Prayaag Venkat (Harvard)

  41. Matroid Partition Property and the Secretary Problem

    Authors: Dorna Abdolazimi, Anna Karlin, Nathan Klein, Shayan Oveis Gharan (University of Washington)

  42. A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators

    Authors: Idan Attias (Ben-Gurion University); Edith Cohen (Google and Tel Aviv University); Moshe Shechner (Tel Aviv University); Uri Stemmer (Google and Tel Aviv University)

  43. Asynchronous Multi-Party Quantum Computation

    Authors: Vipul Goyal (Carnegie Mellon University and NTT Research); Chen-Da Liu-Zhang (NTT Research); Justin Raizes, Joao Ribeiro (Carnegie Mellon University)

  44. Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

    Authors: Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang (University of Texas at Austin)

  45. Karchmer-Wigderson Games for Hazard-free Computation

    Authors: Christian Ikenmeyer (University of Liverpool, United Kingdom.); Balagopal Komarath (IIT Gandhinagar, Gujarat, India); Nitin Saurabh (IIT Hyderabad, India.)

  46. Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique

    Authors: Pasin Manurangsi (Google Research)

  47. Garland’s Technique for Posets and High Dimensional Grassmannian Expanders

    Authors: Tali Kaufman (BIU); Ran J. Tessler (Weizmann Institute of Science)

  48. Bit Complexity of Jordan Normal Form and Spectral Factorization

    Authors: Nikhil Srivastava (UC Berkeley); Ravindran Kannan (Microsoft Reseach India); Nick Ryder (OpenAI); Papri Dey (Georgia Tech)

  49. Epic Fail: Emulators can tolerate some edge faults for free

    Authors: Greg Bodwin (University of Michigan); Michael Dinitz (Johns Hopkins University); Yasamin Nazari (University of Salzburg)

  50. On computing homological hitting sets

    Authors: Ulrich Bauer (Technical University of Munich); Abhishek Rathod (Purdue University); Meirav Zehavi (Ben-Gurion University)

  51. Decision Making under Miscalibration

    Authors: Guy Rothblum (Apple); Gal Yona (Weizmann Institute of Science)

  52. Graph Searching with Predictions

    Authors: Siddhartha Banerjee (Cornell); Vincent Cohen-Addad (Google); Anupam Gupta (Carnegie Mellon); Zhouzi Li (Tsinghua University)

  53. Making Auctions Robust to Aftermarkets

    Authors: Moshe Babaioff, Nicole Immorlica (Microsoft Research); Yingkai Li (Yale University); Brendan Lucier (Microsoft Research New England)

  54. HappyMap: A Generalized Multicalibration Method

    Authors: Zhun Deng, Cynthia Dwork (Harvard University); Linjun Zhang (Rutgers University)

  55. Is Untrusted Randomness Helpful?

    Authors: Uma Girish, Ran Raz, Wei Zhan (Princeton University)

  56. Worst-Case to Expander-Case Reductions

    Authors: Amir Abboud, Nathan Wallheimer (Weizmann Institute)

  57. On disperser/lifting properties of the Index and Inner-Product functions

    Authors: Paul Beame (University of Washington); Sajin Koroth (University of Victoria)

  58. Counting Subgraphs in Somewhere Dense Graphs

    Authors: Marco Bressan (University of Milan); Leslie Ann Goldberg (University of Oxford); Kitty Meeks (University of Glasgow); Marc Roth (University of Oxford)

  59. Consensus Division in an Arbitrary Ratio

    Authors: Paul W. Goldberg (University of Oxford); Jiawei Li (University of Texas at Austin)

  60. Quantum Proofs of Deletion for Learning with Errors

    Authors: Alexander Poremba (California Institute of Technology)

  61. Differentially Private Continual Releases of Streaming Frequency Moment Estimations

    Authors: Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, Peilin Zhong (Google Research)

  62. Generalized Private Selection and Testing with High Confidence

    Authors: Edith Cohen (Google Research and Tel Aviv University); Xin Lyu (UC Berkeley); Jelani Nelson (UC Berkeley & Google Research); Tamás Sarlós (Google Research); Uri Stemmer (Tel Aviv University and Google Research)

  63. Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes

    Authors: Lunjia Hu, Charlotte Peale (Stanford University)

  64. List Agreement Expansion from Coboundary Expansion

    Authors: Roy Gotlib, Tali Kaufman (Bar-Ilan University)

  65. TFNP Characterizations of Proof Systems and Monotone Circuits

    Authors: Noah Fleming (Memorial University); Sam Buss, Russell Impagliazzo (University of California, San Diego)

  66. All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method

    Authors: Sepehr Assadi, Aaron Bernstein, Zachary Langley (Rutgers University)

  67. What Can Cryptography Do For Decentralized Mechanism Design?

    Authors: Elaine Shi, Hao Chung, Ke Wu (Carnegie Mellon University)

  68. The Complexity of Infinite-Horizon General-Sum Stochastic Games

    Authors: Yujia Jin (Stanford University); Vidya Muthukumar (Georgia Institute of Technology); Aaron Sidford (Stanford University)

  69. Black-box Constructive Proofs are Unavoidable

    Authors: Lijie Chen (UC Berkeley); Ryan Williams (MIT); Tianqi Yang (Tsinghua University)

  70. Online Pen Testing

    Authors: Mingda Qiao, Gregory Valiant (Stanford University)

  71. False Consensus, Information Theory, and Prediction Markets

    Authors: Yuqing Kong (Peking University); Grant Schoenebeck (University of Michigan)

  72. Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence

    Authors: Jason Gaitonde (Cornell University); Yingkai Li (Yale University); Bar Light (Microsoft Research New York City); Brendan Lucier (Microsoft Research New England); Aleksandrs Slivkins (Microsoft Research New York City)

  73. New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method

    Authors: Lijie Chen (UC Berkeley)

  74. Recovery from Non-Decomposable Distance Oracles

    Authors: Zhuangfei Hu (Unafilliated); Xinda Li (University of Waterloo); David Woodruff (Carnegie Mellon University); Hongyang Zhang, Shufan Zhang (University of Waterloo)

  75. On Identity Testing and Noncommutative Rank Computation over the Free Skew Field

    Authors: V. Arvind (Institute of Mathematical Sciences (HBNI), Chennai); Abhranil Chatterjee (Indian Institute of Technology Bombay, India); Utsab Ghosal, Partha Mukhopadhyay (Chennai Mathematical Institute); Ramya C (Institute of Mathematical Sciences)

  76. Rigidity in Mechanism Design and its Applications

    Authors: Shahar Dobzinski, Ariel Shaulker (Weizmann Institute)

  77. Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations

    Authors: Anurag Anshu (Harvard University); Tony Metger (ETH Zurich)

  78. Secure Distributed Network Optimization Against Eavesdroppers

    Authors: Yael Hitron, Merav Parter (Weizmann Institute); Eylon Yogev (Bar-Ilan University)

  79. Private Counting of Distinct and k-Occurring Items in Time Windows

    Authors: Badih Ghazi, Ravi Kumar (Google); Pasin Manurangsi (Google Research); Jelani Nelson (UC Berkeley & Google Research)

  80. Is This Correct? Let's Check!

    Authors: Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel (MIT); Madhu Sudan (Harvard University)

  81. Efficiently Testable Circuits

    Authors: Mirza Ahad Baig (ISTA); Suvradip Chakraborty (ETH Zurich); Stefan Dziembowski (University of Warsaw and IDEAS NCBR); Małgorzata Gałązka (University of Warsaw); Tomasz Lizurej (University of Warsaw and IDEAS NCBR); Krzysztof Pietrzak (ISTA)

  82. Clustering Permutations: New Techniques with Streaming Applications

    Authors: Diptarka Chakraborty (National University of Singapore); Debarati Das (Pennsylvania State University); Robert Krauthgamer (Weizmann Institute of Science)

  83. Certificate games

    Authors: Sourav Chakraborty (Indian Statistical Institute (ISI) , Kolkata, India); Anna Gal (University of Texas at Austin); Sophie Laplante (Université Paris Cité); Rajat Mittal (Indian Institute of Technology Kanpur); Anupa Sunny (Université Paris Cité)

  84. The Strength of Equality Oracles in Communication

    Authors: Toniann Pitassi (Columbia University); Morgan Shirley (University of Toronto); Adi Shraibman (The Academic College of Tel Aviv-Yaffo)

  85. Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments

    Authors: Varun Gupta (University of Chicago); Ravishankar Krishnaswamy (Microsoft Research India); Sai Sandeep (Carnegie Mellon University); Janani Sundaresan (Rutgers University)

  86. A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit

    Authors: Hamza Fawzi (University of Cambridge); Omar Fawzi (Inria, ENS de Lyon); Samuel Scalet (University of Cambridge)

  87. An Improved Lower Bound for Matroid Intersection Prophet Inequalities

    Authors: Raghuvansh Saxena (Microsoft Research); Santhoshini Velusamy (Harvard University); S. Matthew Weinberg (Princeton University)

  88. Quantum majority vote

    Authors: Harry Buhrman (QuSoft, CWI, University of Amsterdam); Noah Linden (University of Bristol); Laura Mančinska (University of Copenhagen); Ashley Montanaro (Phasecraft Ltd, University of Bristol); Maris Ozols (QuSoft, University of Amsterdam)

  89. Downward self-reducibility in TFNP

    Authors: Prahladh Harsha (TIFR, Mumbai); Daniel Mitropolsky (Columbia University); Alon Rosen (Bocconi University and Reichman University)

  90. On Low-End Obfuscation and Learning

    Authors: Elette Boyle (Reichman University and NTT Research); Yuval Ishai (Technion); Pierre Meyer (Reichman University and IRIF, Université Paris Cité, CNRS); Robert Robere (McGill); Gal Yehuda (Technion)

  91. Resilience of 3-Majority Dynamics to Non-Uniform Schedulers

    Authors: Uri Meir, Rotem Oshman, Ofer Shayevitz, Yuval Volkov (Tel Aviv University)

  92. An Algorithmic Bridge Between Hamming and Levenshtein Distances

    Authors: Elazar Goldenberg (The Academic College of Tel Aviv-Yaffo); Tomasz Kociumaka (Max Planck Institute for Informatics); Robert Krauthgamer (Weizmann Institute of Science); Barna Saha (University of California San Diego)

  93. Lifting to Parity Decision Trees via Stifling

    Authors: Arkadev Chattopadhyay (TIFR, Mumbai); Nikhil S. Mande (CWI and QuSoft, Amsterdam); Swagato Sanyal (IIT Kharagpur); Suhail Sherif (Vector Institute, Toronto)

  94. Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

    Authors: Gillat Kol (Princeton University); Dmitry Paramonov (Princeton University); Raghuvansh Saxena (Microsoft Research); Huacheng Yu (Princeton University)

  95. Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds

    Authors: Klim Efremenko (Ben-Gurion University); Gillat Kol, Dmitry Paramonov (Princeton University); Raghuvansh R. Saxena (Microsoft Research)

  96. Constant-depth sorting networks

    Authors: Natalia Dobrokhotova-Maikova (Yandex, Moscow, Russia); Alexander Kozachinskiy (Institute for Mathematical and Computational Engineering, Universidad Católica de Chile \ IMFD & CENIA Chile, Santiago, Chile); Vladimir Podolskii (Courant Institute of Mathematical Sciences, New York University, NY, USA)

  97. Algorithms with More Granular Differential Privacy Guarantees

    Authors: Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thomas Steinke (Google Research)

  98. Bootstrapping Homomorphic Encryption via Functional Encryption

    Authors: Nir Bitansky, Tomer Solomon (Tel Aviv University)

  99. On Flipping the Fréchet distance

    Authors: Omrit Filtser (The Open University of Israel); Mayank Goswami (Queens College, City University of New York); Joseph Mitchell (Stony Brook University); Valentin Polishchuk (Linkoping University)

  100. Communication Complexity of Inner Product in Symmetric Normed Spaces

    Authors: Jaroslaw Blasiok, Alexandr Andoni (Columbia University); Arnold Filtser (Bar Ilan University)

  101. Is it easier to count communities than find them?

    Authors: Cynthia Rush (Columbia); Fiona Skerman (Uppsala University); Alexander S Wein (UC Davis); Dana Yang (Cornell)