ITCS 2023 Program and Schedule

Welcome to ITCS 2023. The conference will run in a single track and all sessions will take place at the Stata center room 32-G449 and overflow room 32-D463.
All times are in EST.

Tuesday, January 10th
9:40am - 9:50am Yael Kalai	Welcoming remarks.
Session 1 9:50am-10:50am Chair: Raghuvansh Saxena	Exponential separations using guarded extension variables Video Authors: Emre Yolcu, Marijn Heule (Carnegie Mellon University) Certificate games Video 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é) Downward self-reducibility in TFNP Video Authors: Prahladh Harsha (TIFR, Mumbai); Daniel Mitropolsky (Columbia University); Alon Rosen (Bocconi University and Reichman University) Extremal Combinatorics, iterated pigeonhole arguments, and generalizations of PPP Video Authors: Amol Pasarkar, Christos Papadimitriou, Mihalis Yannakakis (Columbia University) PPP-Completeness and Extremal Combinatorics Video 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)
Session 2 11:00am-12:00pm Chair: John Wright	Rigidity for Monogamy-of-Entanglement Games Authors: Anne Broadbent, Eric Culf (University of Ottawa) Quantum algorithms and the power of forgetting Video Authors:Amin Shiraz Gilani, Andrew M. Childs, Matthew Coudron (University of Maryland) Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement Video Authors: Dorian Rudolph, Sevag Gharibian (Universität Paderborn) Unitary property testing lower bounds by polynomials Video Authors: Adrian She (University of Toronto); Henry Yuen (Columbia University) Fractional certificates for bounded functions Video Authors: Shachar Lovett (University of California San Diego); Jiapeng Zhang (University of Southern California)
12:00pm- 1:40pm	Lunch break (on your own).
Session 3 1:40pm-2:40pm Chair: Alex Lombardi	Learning versus Pseudorandom Generators in Constant Parallel Time Video Authors: Shuichi Hirahara (National Institute of Informatics); Mikito Nanashima (Tokyo Institute of Technology) Kolmogorov Complexity Characterizes Statistical Zero Knowledge Video Authors: Eric Allender (Rutgers University); Shuichi Hirahara (National Institute of Informatics); Harsha Tirumala (Rutgers University) 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) Bootstrapping Homomorphic Encryption via Functional Encryption Video Authors: Nir Bitansky, Tomer Solomon (Tel Aviv University) Incompressiblity and Next-Block Pseudoentropy Video Authors: Iftach Haitner, Noam Mazor, Jad Silbak (Tel Aviv University)
Session 4 2:50pm-3:50pm Chair: Raghuvansh Saxena	Differentially Private Continual Releases of Streaming Frequency Moment Estimations Video Authors: Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, Peilin Zhong (Google Research) A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators Video 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) Expander Decomposition in Dynamic Streams Video Authors: Arnold Filtser (Bar-Ilan University); Michael Kapralov, Mikhail Makarov (EPFL) All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method Video Authors: Sepehr Assadi, Aaron Bernstein, Zachary Langley (Rutgers University) Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly Video Authors: Gillat Kol (Princeton University), Dmitry Paramonov (Princeton University); Raghuvansh Saxena (Microsoft Research); Huacheng Yu (Princeton University)
3:50pm- 4:20pm	Break.
Session 5 4:20pm-5:30pm Chair: Sam Hopkins	Exact Completeness of LP Hierarchies for Linear Codes Video Authors: Leonardo Nagami Coregliano, Fernando Granha Jeronimo (Institute for Advanced Study); Chris Jones (University of Chicago) Is This Correct? Let's Check! Video Authors: Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel (MIT); Madhu Sudan (Harvard University) An Improved Lower Bound for Matroid Intersection Prophet inequalities Video Authors: Raghuvansh R. Saxena (Microsoft), Santhoshini Velusamy (Harvard University), S. Matthew Weinberg (Princeton University) Matroid Partition Property and the Secretary Problem Video Authors: Dorna Abdolazimi, Anna Karlin, Nathan Klein, Shayan Oveis Gharan (University of Washington) Is Untrusted Randomness Helpful? Video Authors: Uma Girish, Ran Raz, Wei Zhan (Princeton University) Is it easier to count communities than find them? Video Authors: Cynthia Rush (Columbia); Fiona Skerman (Uppsala University); Alexander S Wein (UC Davis); Dana Yang (Cornell)
Wednesday, January 11th
Session 6 10:00am - 11:00am Chair: Nikhil Srivastava	Bit Complexity of Jordan Normal Form and Spectral Factorization Video Authors: Nikhil Srivastava (UC Berkeley); Ravindran Kannan (Microsoft Reseach India); Nick Ryder (OpenAI); Papri Dey (Georgia Tech) Matrix multiplication via matrix groups Video 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) Efficient algorithms for certifying lower bounds on the discrepancy of random matrices Video Authors: Prayaag Venkat (Harvard) Symmetric Formulas for Products of Permutations Video Authors: William He, Benjamin Rossman (Duke University) On Identity Testing and Noncommutative Rank Computation over the Free Skew Field Video 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)
Session 7 11:10am-12:10pm Chair: Avishay Tal	The Strength of Equality Oracles in Communication Video Authors: Toniann Pitassi (Columbia University); Morgan Shirley (University of Toronto); Adi Shraibman (The Academic College of Tel Aviv-Yaffo) Communication Complexity of Inner Product in Symmetric Normed Spaces Authors: Jaroslaw Blasiok, Alexandr Andoni (Columbia University); Arnold Filtser (Bar Ilan University) TFNP Characterizations of Proof Systems and Monotone Circuits Video Authors: Noah Fleming (Memorial University); Sam Buss, Russell Impagliazzo (University of California, San Diego) On disperser/lifting properties of the Index and Inner-Product functions Video Authors: Paul Beame (University of Washington); Sajin Koroth (University of Victoria) Lifting to Parity Decision Trees Via Stifling Video Authors: Arkadev Chattopadhyay (TIFR, Mumbai); Nikhil S. Mande (CWI and QuSoft,amsterdam); Swagato Sanyal (IIT Kharagpur); Suhail Sherif (Vector Institute, Toronto)
12:10pm- 1:50pm	Lunch break (on your own).
Session 8 1:50pm- 2:50pm Chair: John Wright	🏆 Best Student Paper: Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom Video Authors: Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang (University of Texas at Austin) Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations Video Authors: Anurag Anshu (Harvard University); Tony Metger (ETH Zurich) A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit Video Authors: Hamza Fawzi (University of Cambridge); Omar Fawzi (Inria, ENS de Lyon); Samuel Scalet (University of Cambridge) Quantum majority vote Authors: Harry Buhrman (QuSoft, CWI, University ofamsterdam); Noah Linden (University of Bristol); Laura Mančinska (University of Copenhagen); Ashley Montanaro (Phasecraft Ltd, University of Bristol); Maris Ozols (QuSoft, University ofamsterdam) Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses Video Authors: Chris Jones, Kunal Marwaha (University of Chicago); Juspreet Singh Sandhu (Harvard University); Jonathan Shi (Bocconi University)
Session 9 3:00pm-3:50pm Chair: Brendan Lucier	Beyond Worst-Case Budget-Feasible Mechanism Design Video Authors: Aviad Rubinstein, Junyao Zhao (Stanford University) Strategyproof Scheduling with Predictions Video Authors: Eric Balkanski (Columbia University); Vasilis Gkatzelis, Xizhi Tan (Drexel University) Opponent Indifference in Rating Systems: A Theoretical Case for Sonas Video Authors: Greg Bodwin, Forest Zhang (University of Michigan) The Complexity of Infinite-Horizon General-Sum Stochastic Games Video Authors: Yujia Jin (Stanford University); Vidya Muthukumar (Georgia Institute of Technology); Aaron Sidford (Stanford University)
3:50pm- 4:20pm	Break.
Session 10 4:20pm- 5:10pm Chair: Adam Smith	Necessary Conditions in Multi-Server Differential Privacy Video Authors: Albert Cheu, Chao Yan (Georgetown University) Generalized Private Selection and Testing with High Confidence Video 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) Private Counting of Distinct and k-Occurring Items in Time Windows Video Authors: Badih Ghazi, Ravi Kumar (Google); Pasin Manurangsi (Google Research); Jelani Nelson (UC Berkeley & Google Research) Algorithms with More Granular Differential Privacy Guarantees Video Authors: Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thomas Steinke (Google Research)
Session 11 5:20pm-6:00pm Chair: Adam Smith	Loss Minimization through the lens of Outcome Indistinguishability Video Authors: Parikshit Gopalan (Apple); Lunjia Hu (Stanford University); Michael P. Kim (UC Berkeley); Omer Reingold (Stanford University); Udi Wieder (VMware) HappyMap: A Generalized Multicalibration Method Video Authors: Zhun Deng, Cynthia Dwork (Harvard University); Linjun Zhang (Rutgers University) Decision Making under Miscalibration Video Authors: Guy Rothblum (Apple); Gal Yona (Weizmann Institute of Science)
6:00pm- 8:00pm	Graduating Bits and Pizza 🍕 🍕 🍕 (in 32-G449).
Thursday, January 12th
Session 12 10:00am-11:00am Chair: Avishay Tal	On Oracles and Algorithmic Methods for Proving Lower Bounds Video Authors: Nikhil Vyas, Ryan Williams (MIT) Karchmer-Wigderson Games for Hazard-free Computation Video Authors: Christian Ikenmeyer (University of Liverpool, United Kingdom.); Balagopal Komarath (IIT Gandhinagar, Gujarat, India); Nitin Saurabh (IIT Hyderabad, India.) Black-box Constructive Proofs are Unavoidable Video Authors: Lijie Chen (UC Berkeley); Ryan Williams (MIT); Tianqi Yang (Tsinghua University) New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method Video Authors: Lijie Chen (UC Berkeley) A New Conjecture on Hardness of Low-Degree 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems Video Authors: Julia Chuzhoy (Toyota Technological Institute at Chicago); Mina Dalirrooyfard (MIT); Vadim Grinberg (Weizmann Institute of Science); Zihan Tan (Rutgers University)
Session 13 11:10am - 12:10pm Chair: Ankur Moitra	Certification with an NP Oracle Video Authors: Guy Blanc, Caleb Koch (Stanford University); Jane Lange (MIT); Carmen Strassle, Li-Yang Tan (Stanford University) 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) Consensus Division in an Arbitrary Ratio Video Authors: Paul W. Goldberg (University of Oxford); Jiawei Li (University of Texas at Austin) Unsplittable Euclidean Capacitated Vehicle Routing: A 2+\epsilon)(2+ϵ)-Approximation Algorithm Video Authors: Fabrizio Grandoni (IDSIA, University of Lugano); Claire Mathieu (CNRS); Hang Zhou (École Polytechnique) Clustering Permutations: New Techniques with Streaming Applications Video Authors: Diptarka Chakraborty (National University of Singapore); Debarati Das (Pennsylvania State University); Robert Krauthgamer (Weizmann Institute of Science)
12:10pm- 1:50pm	Lunch break (on your own).
Session 14 1:50pm-2:50pm Chair: Brendan Lucier	Learning Reserve Prices in Second-Price Auctions Video Authors: Yaonan Jin (Columbia University); Pinyan Lu (Shanghai University of Finance and Economics); Tao Xiao (Huawei TCS Lab) What Can Cryptography Do For Decentralized Mechanism Design? Video Authors: Elaine Shi, Hao Chung, Ke Wu (Carnegie Mellon University) Making Auctions Robust to Aftermarkets Video Authors: Moshe Babaioff, Nicole Immorlica (Microsoft Research); Yingkai Li (Yale University); Brendan Lucier (Microsoft Research New England) Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence Video 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) Rigidity in Mechanism Design and its Applications Authors: Shahar Dobzinski, Ariel Shaulker (Weizmann Institute)
Session 15 3:00pm-4:00pm Chair: Alex Lombardi	Proofs of Quantumness from Trapdoor Permutations Video Authors: Tomoyuki Morimae (Kyoto University); Takashi Yamakawa (NTT Social Informatics Laboratories) Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and more Qipeng Liu (Simons Institute) On the computational hardness needed for quantum cryptography Video Authors: Zvika Brakerski (Weizmann Institute of Science); Ran Canetti, Luowen Qian (Boston University) Asynchronous Multi-Party Quantum Computation Video Authors: Vipul Goyal (Carnegie Mellon University and NTT Research); Chen-Da Liu-Zhang (NTT Research); Justin Raizes, Joao Ribeiro (Carnegie Mellon University) Quantum Proofs of Deletion for Learning with Errors Video Authors: Alexander Poremba (California Institute of Technology)
4:00pm- 4:30pm	Break.
Session 16 4:30pm-5:30pm Chair: Ankur Moitra	A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems Video Authors: Monika Henzinger (University of Vienna); Billy Jin (Cornell University); Richard Peng (Carnegie Mellon University and University of Waterloo); David Williamson (Cornell University) Vertex Sparsification for Edge Connectivity in Polynomial Time Video Authors: Yang P. Liu (Stanford University) On computing homological hitting sets Video Authors: Ulrich Bauer (Technical University of Munich); Abhishek Rathod (Purdue University); Meirav Zehavi (Ben-Gurion University) Worst-Case to Expander-Case Reductions Video Authors:amir Abboud, Nathan Wallheimer (Weizmann Institute) Counting Subgraphs in Somewhere Dense Graphs Video Authors: Marco Bressan (University of Milan); Leslie Ann Goldberg (University of Oxford); Kitty Meeks (University of Glasgow); Marc Roth (University of Oxford)
5:30pm- 7:30pm	Posters and Reception (in R&D Commons).
Friday, January 13th
Session 17 10:00am - 10:50am Chair: Adam Kalai	🏆 Best Student Paper: Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes Video Authors: Lunjia Hu, Charlotte Peale (Stanford University) Online Learning and Bandits with Queried Hints Video Authors: Aditya Bhaskara (University of Utah); Sreenivas Gollapudi (Google); Sungjin Im (University of California-Merced); Kostas Kollias (Google); Kamesh Munagala (Duke University) Making Decisions under Outcome Performativity Video Authors: Michael P. Kim, Juan C. Perdomo (UC Berkeley) Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique Video Authors: Pasin Manurangsi (Google Research)
Session 18 11:00am-12:20pm Chair: Mohsen Ghaffari	Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks Video Authors: Antoine El-Hayek, Monika Henzinger (University of Vienna); Stefan Schmid (University of Vienna & TU Berlin) The Time Complexity of Consensus Under Oblivious Message Adversaries Video 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) False Consensus, Information Theory, and Prediction Markets Video Authors: Yuqing Kong (Peking University); Grant Schoenebeck (University of Michigan) Secure Distributed Network Optimization Against Eavesdroppers Video Authors: Yael Hitron, Merav Parter (Weizmann Institute); Eylon Yogev (Bar-Ilan University) Resilience of 3-Majority Dynamics to Non-Uniform Schedulers Video Authors: Uri Meir, Rotem Oshman, Ofer Shayevitz, Yuval Volkov (Tel Aviv University) Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds Video Authors: Klim Efremenko (Ben-Gurion University); Gillat Kol, Dmitry Paramonov (Princeton University); Raghuvansh R. Saxena (Microsoft Research) Beeping Shortest Paths via Hypergraph Bipartite Decomposition Video Authors: Fabien Dufoulon (University of Houston); Yuval Emek (Technion); Ran Gelles (Bar-Ilan University)
12:20pm- 2:00pm	Lunch break (on your own).
Session 19 2:00pm-2:50pm Chair: Aaron Sidford	Epic Fail: Emulators can tolerate some edge faults for free Video Authors: Greg Bodwin (University of Michigan); Michael Dinitz (Johns Hopkins University); Yasamin Nazari (University of Salzburg) Graph Searching with Predictions Video Authors: Siddhartha Banerjee (Cornell); Vincent Cohen-Addad (Google); Anupam Gupta (Carnegie Mellon); Zhouzi Li (Tsinghua University) Rounding via Low Dimensional Embeddings Video Authors: Mark Braverman (Princeton University); Dor Minzer (MIT) Garland’s Technique for Posets and High Dimensional Grassmannian Expanders Authors: Tali Kaufman (BIU); Ran J. Tessler (Weizmann Institute of Science)
Session 20 3:00pm-3:50pm Chair: Sofya Raskhodnikova	On Interactive Proofs of Proximity with Proof-Oblivious Queries Video Authors: Oded Goldreich (Weizmann Institute of Science); Guy N. Rothblum (Apple); Tal Skverer (Weizmann Institute of Science) Efficiently Testable Circuits Video 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) List Agreement Expansion from Coboundary Expansion Video Authors: Roy Gotlib, Tali Kaufman (Bar-Ilan University) Improved Monotonicity Testing Over the Hypergrid via Hypercube Embeddings Video Authors: Mark Braverman (Princeton University), Subhash Khot (NYU); Guy Kindler (Hebrew University of Jerusalem); Dor Minzer (MIT)
3:50pm- 4:20pm	Break.
Session 21 4:20pm-5:20pm Chair: Aaron Sidford	Online Pen Testing Video Authors: Mingda Qiao, Gregory Valiant (Stanford University) Recovery from Non-Decomposable Distance Oracles Video Authors: Zhuangfei Hu (Unafilliated); Xinda Li (University of Waterloo); David Woodruff (Carnegie Mellon University); Hongyang Zhang, Shufan Zhang (University of Waterloo) An Algorithmic Bridge Between Hamming and Levenshtein Distances Video 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) Constant-depth sorting networks Video 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) Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments Video Authors: Varun Gupta (University of Chicago); Ravishankar Krishnaswamy (Microsoft Research India); Sai Sandeep (Carnegie Mellon University); Janani Sundaresan (Rutgers University)

Finito la comedia!