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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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!