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.


All timings are in Eastern Standard Time (EST).

Tuesday, January 7th
9:00am- 9:25am Coffee and Check-in
9:25am - 9:30am
 		Welcome remarks.
Session 1
9:30am-10:40am
Chair: TBD
  • The Randomness Complexity of Differential Privacy
    Clement Canonne (University of Sydney); Francis E. Su (Harvey Mudd College); Salil P. Vadhan (Harvard University)

  • Locally Private Histograms in All Privacy Regimes
    Abigail Gentle (The University of Sydney); Clement Canonne (University of Sydney)

  • Differential Privacy on Trust Graphs
    Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Serena Wang (Google)

  • Differential privacy and Sublinear time are incompatible sometimes
    Jeremiah Blocki (Purdue University); Hendrik Fichtenberger (Google Research); Elena Grigorescu (Purdue University); Tamalika Mukherjee (Columbia University)

  • 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)

  • Extracting Dual Solutions via Primal Optimizers
    Yair Carmon (Tel Aviv University); Arun Jambulapati (Simons Institute); Liam O'Carroll, Aaron Sidford (Stanford University)

10:40am- 11:10am Break (Coffee and Refreshments)
Session 2
11:10am-12:30pm
Chair: TBD
  • List Decoding Bounds for Binary Codes with Noiseless Feedback
    Rachel Yun Zhang (MIT); Meghal Gupta (UC Berkeley)

  • Error-Correcting Graph Codes
    Swastik Kopparty (University of Toronto); Aditya Potukuchi (York University); Harry Sha (University of Toronto)

  • 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)

  • 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)

  • Randomly Punctured Polynomial Ideal Codes are List Decodable with Optimal List Size
    Noga Ron-Zewi, S. Venkitesh (University of Haifa); Mary Wootters (Stanford University, USA)

  • 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)

12:30pm-2:00pm Lunch break (on your own).
Session 3
2:00pm-3:10pm
Chair: TBD
  • 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)

  • Optimal Communication Complexity of Chained Index
    Janani Sundaresan (University of Waterloo)

  • Separations and lower bounds in parallel query complexity
    Joseph Carolan, Amin Shiraz Gilani, Mahathi Vempati (University of Maryland, College Park)

  • Randomized Lifting to Semi-Structured Communication Complexity via Linear Diversity
    Alexander Shekhovtsov (Moscow Institute of Physics and Technology); Vladimir Podolskii (Tufts University)

  • Catalytic Communication
    Nathan S. Sheffield, Edward Pyne, William Wang (MIT)

  • Characterizing Lossy Catalytic Computation
    Marten Joran Folkertsma (Qusoft, CWI); Ian Mertz (University of Warwick); Florian Speelman (QuSoft, University of Amsterdam); Quinten Tupker (CWI)

3:10pm- 3:50pm Break (Coffee and Refreshments)
Session 4
3:50pm-5:00pm
Chair: TBD
  • Sparsity Lower Bounds for Probabilistic Polynomials
    Josh Alman (Columbia University); Arkadev Chattopadhyay (TIFR, Mumbai); Ryan Williams (MIT)

  • 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)

  • 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)

  • 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)

5:00pm-6:00pm Business Meeting and Reception

Wednesday, January 8th
9:00am- 9:30am Coffee and Check-in
Session 5
9:30am - 10:40am
Chair: TBD
  • New Direct Sum Tests
    Alek Westover, Kai Zhe Zheng, Edward Yu (MIT)

  • Random Restrictions of Bounded Low Degree Polynomials Are Juntas
    Sreejata Kishor Bhattacharya (Tata Institute of Fundamental Research)

  • Derandomized Squaring: An Analytical Insight into Its True Behavior
    Gal Maor, Gil Cohen, Itay Cohen (Tel Aviv University); Yuval Peled (Hebrew University)

  • New Pseudorandom Generators and Correlation Bounds using Extractors
    Vinayak Kumar (UT Austin)

  • 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)

  • Polynomials, Divided Differences, and Codes
    S. Venkitesh (University of Haifa)

10:40am- 11:10am Break (Coffee and Refreshments)
Session 6
11:10am-12:30pm
Chair: TBD
  • Doubly Sub-linear Interactive Proofs of Proximity
    Guy Rothblum (Apple); Noga Amir, Oded Goldriech (Weizmann)

  • 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)

  • Detecting and Correcting Computationally Bounded Errors: A Simple Construction Under Minimal Assumptions
    Jad Silbak, Daniel Wichs (Northeastern University)

  • Accumulation without Homomorphism
    Benedikt Bünz (New York University); Pratyush Mishra (University of Pennsylvania); Wilson D. Nguyen (Stanford University); William Wang (New York University)

  • Incompressible Functional Encryption
    Rishab Goyal (UW-Madison); Venkata Koppula, Mahesh Sreekumar Rajasree, Aman Verma (Indian Institute of Technology, Delhi)

12:30pm- 2:00pm Lunch break (on your own).
Session 7
2:00pm- 3:20pm
Chair: TBD
  • Quantum Communication Complexity of Classical Auctions
    Aviad Rubinstein, Zixin Zhou (Stanford University)

  • 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)

  • Information Design with Unknown Prior
    Tao Lin (Harvard University); Ce Li (Boston University)

  • Stable Matching with Interviews
    Itai Ashlagi, Jiale Chen, Mohammad Roghani, Amin Saberi (Stanford University)

  • Algorithmic Collusion Without Threats
    Eshwar Ram Arunachaleswaran, Natalie Collina, Sampath Kannan, Aaron Roth (University of Pennsylvania); Juba Ziani (Georgia Institute of Technology)

  • Combinatorial Pen Testing (or Consumer Surplus of Deferred-Acceptance Auctions)
    Aadityan Ganesh (Princeton University); Jason Hartline (Northwestern University)

3:20pm- 3:50pm Break (Coffee and Refreshments)
Session 8
3:50pm-5:00pm
Chair: TBD
  • 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)

  • Completeness Theorems for $k$-SUM and Geometric Friends: Deciding fragments of Linear Integer Arithmetic
    Geri Gokaj, Marvin Künnemann (Karlsruhe Institute of Technology)

  • Fine-Grained Equivalence for Problems Related to Integer Linear Programming
    Lars Rohwedder (Mastricht University); Karol Wegrzycki (Saarland University and Max Planck Institute for Informatics)

  • Partial Minimum Branching Program Size Problem is ETH-hard
    Ludmila Glinskih (Google); Artur Riazanov (EPFL)

  • The Computational Complexity of Factored Graphs
    Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, Christopher Ye (University of California, San Diego)

  • 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)

Thursday, January 9th
9:00am- 9:30am Coffee and Check-in
Session 9
9:30am-10:40am
TBD
  • When to Give Up on a Parallel Implementation
    Alek Westover, Nathan S. Sheffield (MIT)

  • Online Balanced Allocation of Dynamic Components
    Rajmohan Rajaraman, Omer Wasim (Northeastern University, USA)

  • 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)

  • Diversity in Evolutionary Dynamics
    Yuval Rabani (Hebrew University); Leonard Schulman (Caltech); Alistair Sinclair (University of California Berkeley)

  • Simple is COOL: Graded Dispersal and its Applications for Byzantine Fault Tolerance
    Ittai Abraham (Intel); Gilad Asharov, Anirudh Chandramouli (Bar-Ilan University)

  • Polynomial Size, Short-Circuit Resilient Circuits for NC
    Yael Tauman Kalai (Microsoft Research and MIT); Raghuvansh R. Saxena (Tata Institute of Fundamental Research)

10:40am- 11:10am Break (Coffee and Refreshments)
Session 10
11:10am - 12:20pm
Chair: TBD
  • A universal sequence of tensors for the asymptotic rank conjecture
    Petteri Kaski (Aalto University); Mateusz Michałek (Universität Konstanz)

  • A high dimensional Cramer's rule connecting homogeneous multilinear equations to hyperdeterminants
    Antoine Joux (CISPA – Helmholtz Center for Information Security); Anand Kumar (Sandbox AQ)

  • 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)

  • 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)

  • 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)

12:20pm- 2pm Graduating Bits and Pizza 🍕 🍕 🍕
Session 11
2pm-3:10pm
Chair: TBD
  • Data-Driven Solution Portfolios
    Marina Drygala (EPFL); Silvio Lattanzi (Google); Andreas Maggiori (Columbia University); Miltiadis Stouras, Ola Svensson (EPFL); Sergei Vassilvitskii (Google Research, USA)

  • Sampling List Packings
    Evan Camrud (Middlebury College); Ewan Davies, Alex Karduna (Colorado State University); Holden Lee (Johns Hopkins University)

  • 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)

  • Unraveling Universally Closest Refinements via Symmetric Density Decomposition and Fisher Market Equilibrium
    T-H. Hubert Chan, Quan Xue (University of Hong Kong)

  • Deterministic approximation for the volume of the truncated fractional matching polytope
    Heng Guo, Vishvajeet N (University of Edinburgh)

  • Facility Location on High-dimensional Euclidean Spaces
    Euiwoong Lee (University of Michigan); Kijun Shin (Seoul National University)

3:10pm- 3:50pm Break (Coffee and Refreshments)
Session 12
3:50pm-5:00pm
Chair: TBD
  • 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)

  • 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)

  • Toward Separating QMA from QCMA with a Classical oracle
    Mark Zhandry (NTT Research)

  • Bosonic Quantum Computational Complexity
    Ulysse Chabaud (INRIA); Michael Joseph, Saeed Mehraban, Arsalan Motamedi (Tufts University)

  • Succinct Fermion Data Structures
    Joseph Carolan (University of Maryland, College Park); Luke Schaeffer (University of Waterloo)

Friday, January 10th
9:00am- 9:30am Coffee and Check-in
Session 13
9:30am - 10:40am
Chair: TBD
  • 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)

  • 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)

  • Rank Lower Bounds on Non-local Quantum Computation
    Vahid R. Asadi, Eric Culf (University of Waterloo); Alex May (Perimeter Institute for Theoretical Physics)

  • Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography
    Prabhanjan Ananth, Fatih Kaleoglu (UCSB); Henry Yuen (Columbia University)

  • 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)

  • Formulations and Constructions of Remote State Preparation with Verifiability, with Applications
    Jiayu Zhang (Zhongguancun Laboratory)

10:40am- 11:10am Break (Coffee and Refreshments)
Session 14
11:10am-12:30pm
Chair: TBD
  • 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)

  • Graph Reconstruction via MIS Queries
    Christian Konrad, Conor O'Sullivan, Victor Traistaru (University of Bristol)

  • Error Correction for Message Streams
    Rachel Yun Zhang (MIT); Meghal Gupta (UC Berkeley)

  • Sketching, Moment Estimation, and the L'evy-Khintchine Representation Theorem
    Dingyu Wang, Seth Pettie (University of Michigan)

  • 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)

  • 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)

12:30pm- 2:00pm Lunch break (on your own).
Session 15
2:00pm-3:10pm
Chair: TBD
  • Estimating Euclidean distance to linearity
    Andrej Bogdanov (University of Ottawa); Lorenzo Taschin (École polytechnique fédérale de Lausanne)

  • Adversarially Robust Property Testing: Separations between Online and Offline Models
    Esty Kelman (MIT, Boston University); Ephraim Linder, Sofya Raskhodnikova (Boston University)

  • 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)

  • Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing
    Deeparnab Chakrabarty (Dartmouth); C. Seshadhri (University of California, Santa Cruz)

  • Query Complexity of Stochastic Minimum Vertex Cover
    Mahsa Derakhshan, Mohammad Saneian (Northeastern University)

  • 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)

3:10pm- 3:50pm Break (Coffee and Refreshments)
Session 16
3:50pm-5:00pm
Chair: TBD
  • 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)

  • Low Sensitivity Hopsets
    Chengyuan Deng, Vikrant Ashvinkumar, Aaron Bernstein, Jie Gao (Rutgers University); Nicole Wein (University of Michigan, Ann Arbor, USA)

  • Eulerian orientations and Hadamard codes: A novel connection via counting
    Shuai Shao, Zhuxiao Tang (University of Science and Technology of China)

  • Listing 6-Cycles in Sparse Graphs
    Alek Westover, Virginia Vassilevska Williams (MIT)

  • Edge-Minimum Walk of Modular Length in Polynomial Time
    Antoine Amarilli (Inria Lille); Benoit Groz (Université Paris Saclay); Nicole Wein (University of Michigan)

  • Adjacency Labeling Schemes for Small Classes
    Édouard Bonnet (CNRS, ENS Lyon); Julien Duron (ENS Lyon); John Sylvester, Viktor Zamaraev (University of Liverpool)