ITCS 2024 Program and Schedule

Welcome to ITCS 2025. The conference will run in a single track and all sessions will take place at Columbia Computer Science Building, which can be accessed from the 4th floor of the Mudd Building. For directions and more details see here. You can find preliminary proceedings of the conference here.

All timings are in Eastern Standard Time (EST). Each talk can be at most ten minutes long (including questions).

Tuesday, January 7th
9:00am- 9:25am	Coffee and Check-in
9:25am - 9:30am	Welcome remarks.
Session 1 9:30am-10:40am Chair: Guy Rothblum	The Randomness Complexity of Differential Privacy Clement Canonne (University of Sydney); Francis E. Su (Harvey Mudd College); Salil P. Vadhan (Harvard University) [Video] Locally Private Histograms in All Privacy Regimes Abigail Gentle (The University of Sydney); Clement Canonne (University of Sydney) [Video] Differential Privacy on Trust Graphs Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Serena Wang (Google) [Video] Differential privacy and Sublinear time are incompatible sometimes Jeremiah Blocki (Purdue University); Hendrik Fichtenberger (Google Research); Elena Grigorescu (Purdue University); Tamalika Mukherjee (Columbia University) [Video] Data Reconstruction: When You See It and When You Don't Edith Cohen (Google and Tel Aviv University); Haim Kaplan, Yishay Mansour (Tel Aviv University and Google); Shay Moran (Technion and Google); Kobbi Nissim (Georgetown University); Uri Stemmer (Tel Aviv University and Google); Eliad Tsfadia (Georgetown University) [Video] Extracting Dual Solutions via Primal Optimizers Yair Carmon (Tel Aviv University); Arun Jambulapati (Simons Institute); Liam O'Carroll, Aaron Sidford (Stanford University) [Video]
10:40am- 11:10am	Break (Coffee and Refreshments)
Session 2 11:10am-12:20pm Chair: Guy Rothblum	List Decoding Bounds for Binary Codes with Noiseless Feedback Rachel Yun Zhang (MIT); Meghal Gupta (UC Berkeley) [Video] Error-Correcting Graph Codes Swastik Kopparty (University of Toronto); Aditya Potukuchi (York University); Harry Sha (University of Toronto) [Video] The more the merrier! On total coding and lattice problems and the complexity of finding multicollisions Huck Bennett (University of Colorado Boulder); Surendra Ghentiyala, Noah Stephens-Davidowitz (Cornell University) [Video] Round-vs-Resilience Tradeoffs for Binary Feedback Channels Mark Braverman (Princeton University); Klim Efremenko (Ben-Gurion University); Gillat Kol (Princeton University); Raghuvansh Saxena (Tata Institute of Fundamental Research); Zhijun Zhang (Princeton University) [Video] Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes Nicolas Resch (University of Amsterdam); Chen Yuan (Shanghai Jiao Tong University); Yihan Zhang (Institute of Science and Technology Austria) [Video]
12:30pm-2:00pm	Lunch break (on your own).
Session 3 2:00pm-3:10pm Chair: Guy Rothblum	Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing Xinyu Mao (University of Southern California); Guangxu Yang (University of Southern Califorlia); Jiapeng Zhang (University of Southern California) [Video] Optimal Communication Complexity of Chained Index Janani Sundaresan (University of Waterloo) [Video] Quantum advantage and lower bounds in parallel query complexity Joseph Carolan, Amin Shiraz Gilani, Mahathi Vempati (University of Maryland, College Park) [Video] Randomized Lifting to Semi-Structured Communication Complexity via Linear Diversity Alexander Shekhovtsov (Moscow Institute of Physics and Technology); Vladimir Podolskii (Tufts University) [Video] Catalytic Communication Nathan S. Sheffield, Edward Pyne, William Wang (MIT) [Video] Characterizing Lossy Catalytic Computation Marten Joran Folkertsma (Qusoft, CWI); Ian Mertz (University of Warwick); Florian Speelman (QuSoft, University of Amsterdam); Quinten Tupker (CWI) [Video]
3:10pm- 3:50pm	Break (Coffee and Refreshments)
Session 4 3:50pm-5:00pm Chair: Tal Malkin	Sparsity Lower Bounds for Probabilistic Polynomials Josh Alman (Columbia University); Arkadev Chattopadhyay (TIFR, Mumbai); Ryan Williams (MIT) [Video] Hardness of sampling for the anti-ferromagnetic Ising model on random graphs Neng Huang (University of Michigan); Will Perkins (Georgia Tech); Aaron Potechin (University of Chicago) [Video] A Quantum Unique Games Conjecture Hamoon Mousavi (Simons Institute for Theoretical Computer Science, University of California at Berkeley); Taro Spirig (University of Copenhagen) The Local Hamiltonian problem for quasi-quantum states: A toy model for the quantum PCP conjecture Itai Arad (Centre for Quantum Technologies); Miklos Santha (IRIF, Université de Paris; Centre for Quantum Technologies and Majulab, National University of Singapore) Nearest Neighbor Complexity and Boolean Circuits Daniel Reichman (Worcester Polytechnic Institute); Mason DiCicco (Worcester Polytechinc Institute); Vladimir Podolskii (Tufts University) [Video] Provability of the Circuit Size Hierarchy and Its Consequences Marco Carmosino (IBM Research); Valentine Kabanets (Simon Fraser University); Antonina Kolokolova (Memorial University of Newfoundland); Igor Oliveira, Dimitrios Tsintsilidas (University of Warwick) [Video]
5:00pm-6:00pm	Reception
Wednesday, January 8th
9:00am- 9:30am	Coffee and Check-in
Session 5 9:30am - 10:50am Chair: Toni Pitassi	New Direct Sum Tests Alek Westover, Kai Zhe Zheng, Edward Yu (MIT) [Video] Random Restrictions of Bounded Low Degree Polynomials Are Juntas Best Student Paper Award Sreejata Kishor Bhattacharya (Tata Institute of Fundamental Research) [Video] Derandomized Squaring: An Analytical Insight into Its True Behavior Gal Maor, Gil Cohen, Itay Cohen (Tel Aviv University); Yuval Peled (Hebrew University) [Video] New Pseudorandom Generators and Correlation Bounds using Extractors Vinayak Kumar (UT Austin) [Video] Improved Lower Bounds for 3-Query Matching Vector Codes Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski (National University of Singapore); Sidhant Saraogi (Georgetown University) [Video] Polynomials, Divided Differences, and Codes S. Venkitesh (Tel Aviv University) [Video] Diversity in Evolutionary Dynamics Yuval Rabani (Hebrew University); Leonard Schulman (Caltech); Alistair Sinclair (University of California Berkeley)
10:50am- 11:10am	Break (Coffee and Refreshments)
Session 6 11:10am-12:30pm Chair: Guy Rothblum	Doubly Sub-linear Interactive Proofs of Proximity Guy Rothblum (Apple); Noga Amir, Oded Goldriech (Weizmann) [Video] White-Box Learning of Computationally Shallow Instances Characterizes Public-Key Encryption Yanyi Liu (Cornell Tech); Noam Mazor (Tel Aviv University); Rafael Pass (Tel Aviv University & Cornell Tech) Backdoor defense, learnability and obfuscation Paul Christiano (unaffiliated); Jacob Hilton, Victor Lecomte, Mark Xu (Alignment Research Center) [Video] Detecting and Correcting Computationally Bounded Errors: A Simple Construction Under Minimal Assumptions Jad Silbak, Daniel Wichs (Northeastern University) [Video] Accumulation without Homomorphism Benedikt Bünz (New York University); Pratyush Mishra (University of Pennsylvania); Wilson D. Nguyen (Stanford University); William Wang (New York University) [Video] Incompressible Functional Encryption Rishab Goyal (UW-Madison); Venkata Koppula, Mahesh Sreekumar Rajasree, Aman Verma (Indian Institute of Technology, Delhi) [Video]
12:30pm- 2:00pm	Lunch break (on your own).
Session 7 2:00pm- 3:20pm Chair: Robert Kleinberg	Quantum Communication Complexity of Classical Auctions Aviad Rubinstein, Zixin Zhou (Stanford University) [Video] Robust Restaking Networks Naveen Durvasula, Tim Roughgarden (Columbia University) Confusion Matrix Design for Downstream Decision-making Yiding Feng (Hong Kong University of Science and Technology); Wei Tang (Chinese University of Hong Kong) [Video] Information Design with Unknown Prior Tao Lin (Harvard University); Ce Li (Boston University) [Video] Query Complexity of Stochastic Minimum Vertex Cover Mahsa Derakhshan, Mohammad Saneian (Northeastern University) [Video] Algorithmic Collusion Without Threats Eshwar Ram Arunachaleswaran, Natalie Collina, Sampath Kannan, Aaron Roth (University of Pennsylvania); Juba Ziani (Georgia Institute of Technology) [Video] Combinatorial Pen Testing (or Consumer Surplus of Deferred-Acceptance Auctions) Aadityan Ganesh (Princeton University); Jason Hartline (Northwestern University) [Video]
3:20pm- 3:50pm	Break (Coffee and Refreshments)
Session 8 3:50pm-5:00pm Chair: Ryan Williams	Finite matrix multiplication algorithms from infinite groups Jonah Blasiak (Department of Mathematics, Drexel University); Henry Cohn (Microsoft Research and MIT Dept. of Mathematics); Joshua A. Grochow (Departments of Computer Science and Mathematics, University of Colorado Boulder, Boulder, CO 80309-0430, United States); Kevin Pratt (Courant Institute Department of Computer Science, New York University); Chris Umans (Caltech) [Video] Completeness Theorems for $k$-SUM and Geometric Friends: Deciding fragments of Linear Integer Arithmetic Geri Gokaj, Marvin Künnemann (Karlsruhe Institute of Technology) [Video] Fine-Grained Equivalence for Problems Related to Integer Linear Programming Lars Rohwedder (Mastricht University); Karol Wegrzycki (Saarland University and Max Planck Institute for Informatics) [Video] Partial Minimum Branching Program Size Problem is ETH-hard Ludmila Glinskih (Google); Artur Riazanov (EPFL) [Video] The Computational Complexity of Factored Graphs Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, Christopher Ye (University of California, San Diego) [Video] Parameterized Geometric Graph Modification with Disk Scaling Fedor V. Fomin, Petr A. Golovach (University of Bergen); Tanmay Inamdar (Indian Institute of Technology Jodhpur); Saket Saurabh (IMSc); Meirav Zehavi (Ben-Gurion University of the Negev) [Video]
5:30pm-everyone goes home	Board Games (With Pizza, Refreshments)
Thursday, January 9th
9:00am- 9:30am	Coffee and Check-in
Session 9 9:30am-10:30am Robert Kleinberg	When to Give Up on a Parallel Implementation Alek Westover, Nathan S. Sheffield (MIT) [Video] Online Balanced Allocation of Dynamic Components Rajmohan Rajaraman, Omer Wasim (Northeastern University, USA) [Video] Entry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flows Yudong Chen (University of Wisconsin-Madison); Xumei Xi, Christina Yu (Cornell University) [Video] Simple is COOL: Graded Dispersal and its Applications for Byzantine Fault Tolerance Ittai Abraham (Intel); Gilad Asharov, Anirudh Chandramouli (Bar-Ilan University) [Video] Polynomial Size, Short-Circuit Resilient Circuits for NC Yael Tauman Kalai (Microsoft Research and MIT); Raghuvansh R. Saxena (Tata Institute of Fundamental Research) [Video]
10:30am- 11:10am	Break (Coffee and Refreshments)
Session 10 11:10am - 12:20pm Chair: Josh Alman	A universal sequence of tensors for the asymptotic rank conjecture Petteri Kaski (Aalto University); Mateusz Michałek (Universität Konstanz) [Video] A high dimensional Cramer's rule connecting homogeneous multilinear equations to hyperdeterminants Antoine Joux (CISPA – Helmholtz Center for Information Security); Anand Kumar (Sandbox AQ) [Video] A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions Noga Alon (Princeton University); Nick Gravin (Shanghai University of Finance and Economics); Tristan Pollner, Aviad Rubinstein (Stanford University); Hongao Wang (Purdue University); S. Matthew Weinberg, Qianfan Zhang (Princeton University) [Video] Concentration of Submodular Functions and Read-k Families Under Negative Dependence Sharmila Venkata Sathya Duppala (University of Maryland, College Park); George Li (Carnegie Mellon University); Juan David Luque Chang, Aravind Srinivasan (University of Maryland, College Park, USA); Renata Valieva (University of Maryland) Simple Norm Bounds for Polynomial Random Matrices via Decoupling Madhur Tulsiani (Toyota Technological Institute at Chicago, USA); June Wu (University of Chicago) [Video] A Lower Bound on the Trace Norm of Boolean Matrices and Its Applications Tsun-Ming Cheung, Hamed Hatami (School of Computer Science, McGill University); Kaave Hosseini (Department of Computer Science, University of Rochester); Aleksandar Nikolov (Department of Computer Science, University of Toronto); Toniann Pitassi (Department of Computer Science, Columbia University); Morgan Shirley (Department of Computer Science, University of Toronto) [Video]
12:20pm- 2pm	Graduating Bits and Pizza 🍕 🍕 🍕 [Form to participate]
Session 11 2pm-3:10pm Chair: Alexandr Andoni	Data-Driven Solution Portfolios Marina Drygala (EPFL); Silvio Lattanzi (Google); Andreas Maggiori (Columbia University); Miltiadis Stouras, Ola Svensson (EPFL); Sergei Vassilvitskii (Google Research, USA) [Video] Sampling List Packings Evan Camrud (Middlebury College); Ewan Davies, Alex Karduna (Colorado State University); Holden Lee (Johns Hopkins University) [Video] Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems Matthias Bentert, Fedor V. Fomin (University of Bergen); Tanmay Inamdar (Indian Institute of Technology Jodhpur); Saket Saurabh (IMSc) [Video] Unraveling Universally Closest Refinements via Symmetric Density Decomposition and Fisher Market Equilibrium T-H. Hubert Chan, Quan Xue (University of Hong Kong) [Video] Deterministic approximation for the volume of the truncated fractional matching polytope Heng Guo, Vishvajeet N (University of Edinburgh) [Video] Facility Location on High-dimensional Euclidean Spaces Euiwoong Lee (University of Michigan); Kijun Shin (Seoul National University) [Video]
3:10pm- 3:50pm	Break (Coffee and Refreshments)
Session 12 3:50pm-5:00pm Chair: Henry Yuen	Complexity Classification of Product State Problems for Local Hamiltonians John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang (Sandia National Labs); Justin Yirka (The University of Texas at Austin) [Video] On fault tolerant single-shot logical state preparation and robust long-range entanglement Thiago Bergamaschi (UC Berkeley); Yunchao Liu (Harvard University) Approximate Unitary k-Designs from Shallow, Low-Communication Circuits Nicholas LaRacuente (Indiana University Bloomington); Felix Leditzky (University of Illinois Urbana-Champaign) [Video] Toward Separating QMA from QCMA with a Classical oracle Mark Zhandry (NTT Research) [Video] Bosonic Quantum Computational Complexity Ulysse Chabaud (INRIA); Michael Joseph, Saeed Mehraban, Arsalan Motamedi (Tufts University) [Video] Succinct Fermion Data Structures Joseph Carolan (University of Maryland, College Park); Luke Schaeffer (University of Waterloo) [Video]
5:00pm-6:00pm	Business Meeting
Friday, January 10th
9:00am- 9:30am	Coffee and Check-in
Session 13 9:30am - 10:40am Chair: Supartha Podder	Toward the Impossibility of Perfect Complete Quantum PKE from OWFs Longcheng Li (Institute of Computing Technology, Chinese Academy of Sciences); Qian Li (Shenzhen Research Institute of Big Data); Xingjian Li (Tsinghua University); Qipeng Liu (University of California San Diego) [Video] Quantum 2-SAT on low dimensional systems is QMA_1-complete: Direct embeddings and black-box simulation Dorian Rudolph, Sevag Gharibian (Paderborn University); Daniel Nagaj (Slovak Academy of Sciences) [Video] Rank Lower Bounds on Non-local Quantum Computation Vahid R. Asadi, Eric Culf (University of Waterloo); Alex May (Perimeter Institute for Theoretical Physics) [Video] Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography Prabhanjan Ananth, Fatih Kaleoglu (UCSB); Henry Yuen (Columbia University) [Video] Single-Round Proofs of Quantumness from Knowledge Assumptions Petia Arabadjieva (ETH Zurich); Alexandru Gheorghiu (Chalmers University and IBM Research); Victor Gitton, Tony Metger (ETH Zurich) [Video] Formulations and Constructions of Remote State Preparation with Verifiability, with Applications Jiayu Zhang (Zhongguancun Laboratory) [Video]
10:40am- 11:10am	Break (Coffee and Refreshments)
Session 14 11:10am-12:30pm Chair: Alexandr Andoni	Learning-Augmented Streaming Algorithms for Approximating MAX-CUT Yinhao Dong, Pan Peng (University of Science and Technology of China); Ali Vakilian (Toyota Technological Institute at Chicago) [Video] Graph Reconstruction via MIS Queries Christian Konrad, Conor O'Sullivan, Victor Traistaru (University of Bristol) [Video] Error Correction for Message Streams Best Student Paper Award Rachel Yun Zhang (MIT); Meghal Gupta (UC Berkeley) [Video] Sketching, Moment Estimation, and the L'evy-Khintchine Representation Theorem Dingyu Wang, Seth Pettie (University of Michigan) [Video] Coresets for 1-Center in ell\_1 Metrics Amir Carmel (Weizmann Institute of Science); Chengzhi Guo, Shaofeng H.-C. Jiang (Peking University); Robert Krauthgamer (Weizmann Institute of Science) [Video] Space Complexity of Minimum Cut Problems in Single-Pass Streams Matthew Ding (UC Berkeley); Alexandro Garces (MIT); Jason Li, Honghao Lin (CMU); Jelani Nelson (UC Berkeley); Vihan Shah (University of Waterloo); David P. Woodruff (CMU) [Video]
12:30pm- 2:00pm	Lunch break (on your own).
Session 15 2:00pm-3:10pm Chair: Ryan Williams	Estimating Euclidean distance to linearity Andrej Bogdanov (University of Ottawa); Lorenzo Taschin (École polytechnique fédérale de Lausanne) [Video] Adversarially Robust Property Testing: Separations between Online and Offline Models Esty Kelman (MIT, Boston University); Ephraim Linder, Sofya Raskhodnikova (Boston University) [Video] Settling the complexity of testing grainedness of distributions, and application to uniformity testing in the Huge Object model Clément Canonne (University of Sydney); Sayantan Sen (National University of Singapore); Joy Qiping Yang (University of Sydney) [Video] Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing Deeparnab Chakrabarty (Dartmouth); C. Seshadhri (University of California, Santa Cruz) [Video] Stable Matching with Interviews Itai Ashlagi, Jiale Chen, Mohammad Roghani, Amin Saberi (Stanford University) [Video] Sublinear Metric Steiner Tree via Improved Bounds for Set Cover Sepideh Mahabadi (Microsoft Research); Mohammad Roghani (Stanford University); Jakub Tarnawski (Microsoft Research); Ali Vakilian (Toyota Technological Institute at Chicago) [Video]
3:10pm- 3:50pm	Break (Coffee and Refreshments)
Session 16 3:50pm-5:00pm Chair: Josh Alman	Distributed And Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs Thorsten Götte (Universität Hamburg); Jinfeng Dou, Henning Hillebrandt, Christian Scheideler (Paderborn University); Julian Werthmann (Paderborn University, Germany) [Video] Low Sensitivity Hopsets Chengyuan Deng, Vikrant Ashvinkumar, Aaron Bernstein, Jie Gao (Rutgers University); Nicole Wein (University of Michigan, Ann Arbor, USA) [Video] Eulerian orientations and Hadamard codes: A novel connection via counting Shuai Shao, Zhuxiao Tang (University of Science and Technology of China) [Video] Listing 6-Cycles in Sparse Graphs Alek Westover, Virginia Vassilevska Williams (MIT) [Video] Edge-Minimum Walk of Modular Length in Polynomial Time Antoine Amarilli (Inria Lille); Benoit Groz (Université Paris Saclay); Nicole Wein (University of Michigan) [Video] Adjacency Labeling Schemes for Small Classes Édouard Bonnet (CNRS, ENS Lyon); Julien Duron (ENS Lyon); John Sylvester, Viktor Zamaraev (University of Liverpool) [Video]