ITCS 2022 Program and Schedule

Welcome to ITCS 2022. The conference will run in a single track, held in two zoom rooms. The conference will also have a Gather space for breaks etc. Please remember to [register] to get up-to-date-information and links.
All times are in EST.

January 31st

10:15 AM - 10:30 AM
Mark Braverman
*Room A*
Welcoming remarks.
Session 1.
10:30 AM - 11:30 AM EST
Chair: Igor Oliveira
*Room A*
Small Circuits Imply Efficient Arthur-Merlin Protocols [paper, video]
Michael Ezra and Ron Rothblum (Technion)
Algorithms and Lower Bounds for Comparator Circuits from Shrinkage [paper, video]
Bruno P. Cavalar and Zhenjian Lu (University of Warwick)
A variant of the VC-dimension with applications to depth-3 circuits [paper, video]
Peter Frankl (Rényi Institute); Svyatoslav Gryaznov and Navid Talebanfard (Institute of Mathematics of the Czech Academy of Sciences)
Smaller ACC0 Circuits for Symmetric Functions [paper, video]
Brynmor Chapman and Ryan Williams (MIT)
Almost-Orthogonal Bases for Inner Product Polynomials [paper, video]
Chris Jones and Aaron Potechin (University of Chicago)
Session 2.
11:30 AM - 12:30 PM EST
Chair: Lijie Chen
*Room B*
On Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast Derandomization [paper, video]
Ronen Shaltiel (University of Haifa); Emanuele Viola (Northeastern University)
Errorless versus Error-prone Average-Case Complexity [paper, video]
Shuichi Hirahara (National Institute of Informatics); Rahul Santhanam (University of Oxford)
Reduction From Non-Unique Games to Boolean Unique Games [paper, video]
Ronen Eldan (Weizmann Institute); Dana Moshkowitz (University of Texas at Austin)
Pseudorandom Self-Reductions for NP-Complete Problems [paper, video]
Reyad Abed Elrazik (Technion); Robert Robere (McGill University); Assaf Schuster and Gal Yehuda (Technion)
Excluding PH Pessiland [paper, video]
Shuichi Hirahara (National Institute of Informatics); Rahul Santhanam (University of Oxford)
12:30 PM - 01:00 PM EST BREAK
Session 3.
01:00 PM - 02:00 PM EST
Chair: Mahsa Derakhshan
*Room A*
Dynamic Matching Algorithms Under Vertex Updates [paper, video]
Hung Le (University of Massachusetts); Lazar Milenkovic and Shay Solomon (Tel Aviv University); Virginia Vassilevska Williams (Massachusetts Institute of Technology)
Beating the Folklore Algorithm for Dynamic Matching [paper, video]
Mohammad Roghani, Amin Saberi, and David Wajc (Stanford University)
Deterministic Dynamic Matching In Worst-Case Update Time [paper, video]
Peter Kiss (University of Warwick) (Best Student Paper Award)
Local Access to Random Walks [paper, video]
Amartya Shankha Biswas (MIT); Edward Pyne (Harvard University); Ronitt Rubinfeld (MIT)
Uniform brackets, containers, and combinatorial Macbeath regions [paper, video]
Kunal Dutta (University of Warsaw); Arijit Ghosh (Indian Statistical Institute); Shay Moran (Technion and Google Research)
Session 4.
02:00 PM - 03:00 PM EST
Chair: Yang Cai
*Room B*
Maximizing revenue in the presence of intermediaries [paper, video]
Gagan Aggarwal, Kshipra Bhawalkar Lane, Guru Guruganesh, and Andres Perlroth (Google Research)
Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for all Distributions [paper, video]
Meryem Essaidi, Matheus Venturyne Xavier Ferreira, and S. Matthew Weinberg (Princeton University)
Cursed yet Satisfied Agents [paper, video]
Yiling Chen and Alon Eden (Harvard University); Juntao Wang (GSAS, Harvard)
Mechanism Design with Moral Bidders [paper, video]
Shahar Dobzinski (Weizmann Institute); Sigal Oren (Ben-Gurion University of the Negev)
Optimal Deterministic Clock Auctions and Beyond [paper, video]
George Christodoulou (Univesity of Liverpool); Vasilis Gkatzelis and Daniel Schoepflin (Drexel University)
03:00 PM - 03:30 PM BREAK
Session 5.
03:30 PM - 04:30 PM EST
Chair: Ken Clarkson
*Room A*
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing [paper, video]
Nikhil Bansal (University of Michigan); Haotian Jiang (University of Washington); Raghu Meka (UCLA); Sahil Singla (Georgia Tech); Makrand Sinha (Simons Institute and UC Berkeley)
Budget-Smoothed Analysis for Submodular Maximization [paper, video]
Aviad Rubinstein and Junyao Zhao (Stanford University)
Multiscale entropic regularization for MTS on general metric spaces [paper, video]
Farzam Ebrahimnejad and James R. Lee (University of Washington)
A Spectral Approach to Polytope Diameter [paper, video]
Nikhil Srivastava (UC Berkeley); Hariharan Narayanan (TIFR, Mumbai); Rikhav Shah (UC Berkeley)
Matroid Secretary is Equivalent to Contention Resolution [paper, video]
Shaddin Dughmi (University of Southern California)
Session 6.
04:30 PM - 05:30 PM EST
Chair: Karthik C. S.
*Room B*
Improved Hardness of BDD and SVP Under Gap-(S)ETH [paper, video]
Huck Bennett (Oregon State University); Chris Peikert and Yi Tang (University of Michigan)
3 + ε Approximation of Tree Edit Distance in Truly Subquadratic Time [paper, video]
Masoud Seddighin (Sharif University of Technology); Saeed Seddighin (Toyota Technological Institute at Chicago)
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity [paper, video]
Shyan Akmal, Lijie Chen, and Ce Jin (MIT); Malvika Raj (UC Berkeley); Ryan Williams (MIT)
Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks [paper, video]
Harry Buhrman (QuSoft, CWI, University of Amsterdam); Bruno Loff (University of Porto and INESC-Tec); Subhasree Patro and Florian Speelman (QuSoft, CWI, University of Amsterdam)
Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems [paper, video]
François Le Gall (Nagoya University); Saeed Seddighin (Toyota Technological Institute at Chicago)

February 1st

Session 7.
10:30 AM - 11:30 AM EST
Chair: Frederic Magniez
*Room A*
Lower Bounds on Stabilizer Rank [paper, video]
Shir Peleg and Amir Shpilka (Tel-Aviv University); Ben Lee Volk (UT Austin)
Classical algorithms and quantum limitations for maximum cut on high-girth graphs [paper, video]
Boaz Barak (Harvard University); Kunal Marwaha (Berkeley Center for Quantum Information and Computation)
Eliminating Intermediate Measurements using Pseudorandom Generators [paper, video]
Uma Girish and Ran Raz (Princeton University)
A lower bound on the space overhead of fault-tolerant quantum computation [paper, video]
Omar Fawzi (Inria, ENS Lyon); Alexander Müller-Hermes (Institut Camille Jordan, Université Claude Bernard Lyon 1); Ala Shayeghi (Inria, ENS Lyon)
Quantum Distributed Algorithms for Detection of Cliques [paper, video]
Keren Censor-Hillel (Technion); Orr Fischer (Tel Aviv University); François Le Gall (Nagoya University); Dean Leitersdorf (Technion); Rotem Oshman (Tel Aviv University)
11:30 AM - Noon BREAK
Noon - 01:00 PM EST
Chair: Gautam Kamath
*Room B*
Graduating Bits. [More information about the speakers can be found here.]. [A video recording of the session.]
01:00 PM - 01:30 PM BREAK
Session 8.
01:30 PM - 02:30 PM EST
Chair: Eylon Yogev
*Room A*
Interaction Preserving Compilers for Secure Computation [paper, video]
Nico Döttling (CISPA); Vipul Goyal (NTT Research and CMU); Giulio Malavolta (MPI-SP); Justin Raizes (CMU)
Locality-Preserving Hashing for Shifts with Connections to Cryptography [paper, video]
Elette Boyle (IDC Herzliya); Itai Dinur (Department of Computer Science, Ben-Gurion University, Israel); Niv Gilboa (Ben Gurion University, Israel); Yuval Ishai (Technion); Nathan Keller and Ohad Klein (Bar Ilan University)
Pre-Constrained Encryption [paper, video]
Prabhanjan Ananth (University of California Santa Barbara); Abhishek Jain and Zhengzhong Jin (Johns Hopkins University); Giulio Malavolta (Max Planck Institute for Security and Privacy)
Lattice-Inspired Broadcast Encryption and Succinct Ciphertext-Policy ABE [paper, video]
Zvika Brakerski (Weizmann); Vinod Vaikuntanathan (MIT)
Correlation-Intractable Hash Functions via Shift-Hiding [paper, video]
Alex Lombardi and Vinod Vaikuntanathan (MIT)
Session 9.
02:30 PM - 03:30 PM EST
Chair: Rotem Oshman
*Room B*
Distributed Vertex Cover Reconfiguration [paper, video]
Yannic Maus (TU Graz); Keren Censor-Hillel, Shahar Romem-Peled, and Tigran Tonoyan (Technion)
Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems [paper, video]
Shiri Antaki (Tel Aviv University); Quanquan C. Liu (MIT); Shay Solomon (Tel Aviv University)
Continuous Tasks and the Asynchronous Computability Theorem [paper, video]
Hugo Rincon Galeana (TU Wien); Sergio Rajsbaum (UNAM); Ulrich Schmid (TU Wien)
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics [paper, video]
Sebastian Brandt (CISPA Helmholtz Center for Information Security); Yi-Jun Chang (National University of Singapore); Jan Grebík (Warwick); Christoph Grunau and Václav Rozhoň (ETH Zurich); Zoltán Vidnyánszky (Caltech)
Adaptive Massively Parallel Constant-round Tree Contraction [paper, video]
MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh (University of Maryland); Hsin-Hao Su (Boston College)
03:30 PM - 04:00 PM BREAK
Session 10.
04:00 PM - 05:00 PM EST
Chair: Ariel Schvartzman
*Room A*
Individual Fairness in Advertising Auctions through Inverse Proportionality [paper, video]
Shuchi Chawla (UT Austin); Meena Jagadeesan (UC Berkeley)
On Fairness and Stability in Two-Sided Matchings [paper, video]
Gili Karni (Weizmann institute of science); Guy Rothblum and Gal Yona (Weizmann Institute of Science)
Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu [paper, video]
Mojtaba Hosseini (Paul Merage School of Business, UCI); Vijay Vazirani (University of California, Irvine)
Interactive Communication in Bilateral Trade [paper, video]
Jieming Mao and Renato Paes Leme (Google Research); Kangning Wang (Duke University)
Multi-Channel Bayesian Persuasion [paper, video]
Yakov Babichenko and Inbal Talgam-Cohen (Technion - Israel Institute of Technology); Haifeng Xu (University of Virginia); Konstantin Zabarnyi (Technion - Israel Institute of Technology)
Session 11.
05:00 PM - 06:00 PM EST
Chair: Aditya Bhaskara
*Room B*
Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions [paper, video]
Sepehr Assadi and Chen Wang (Rutgers University)
Symmetric Sparse Boolean Matrix Factorization and Applications [paper, video]
Sitan Chen (UC Berkeley); Zhao Song (Adobe Research); Runzhou Tao (Columbia University); Ruizhe Zhang (The University of Texas at Austin)
Online Multivalid Learning: Means, Moments, and Prediction Intervals [paper, video]
Varun Gupta, Christopher Jung, and Georgy Noarov (University of Pennsylvania); Mallesh M. Pai (Rice University); Aaron Roth (University of Pennsylvania)
Omnipredictors [paper, video]
Parikshit Gopalan (VMware Research); Adam Tauman Kalai (Microsoft Research); Omer Reingold (Stanford); Vatsal Sharan (USC); Udi Wieder (VMware Research)
Optimal Sub-Gaussian Mean Estimation in Very High Dimensions [paper, video]
Jasper C.H. Lee (University of Wisconsin-Madison); Paul Valiant (Purdue University)
Session 12.
06:00 PM - 07:00 PM EST
Chair: Omri Ben-Eliezer
*Room A*
Noisy Boolean Hidden Matching with Applications [paper, video]
Michael Kapralov (EPFL); Amulya Musipatla (CMU); Jakab Tardos (EPFL); David Woodruff and Samson Zhou (CMU)
Adversarially Robust Coloring for Graph Streams [paper, video]
Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl (Dartmouth College)
Optimal Bounds for Dominating Set in Graph Streams [paper, video]
Sanjeev Khanna (University of Pennsylvania); Christian Konrad (University of Bristol)
An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes [paper, video]
Anubhav Baweja, Justin Jia, and David P. Woodruff (Carnegie Mellon University)
An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams [paper, video]
Sepehr Assadi and Vihan Shah (Rutgers University)

February 2nd

09:30 AM - 10:20 AM EST
Chair: Gautam Kamath
*Room A*
Graduating Bits. [More information about the speakers can be found here.]. [A video recording of the session.]
10:20 AM - 10:30 AM BREAK
Session 13.
10:30 AM - 11:30 AM EST
Chair: Josh Alman
*Room B*
Polynomial Identity Testing via Evaluation of Rational Functions [paper, video]
Dieter van Melkebeek and Andrew Morgan (University of Wisconsin–Madison)
Lower Bounds for Symmetric Circuits for the Determinant [paper, video]
Anuj Dawar and Gregory Wilsenach (University of Cambridge)
Symbolic determinant identity testing and non-commutative ranks of matrix Lie algebras [paper, video]
Gábor Ivanyos (Institute for Computer Science and Control, Eötvös Loránd Research Network (ELKH), Budapest, Hungary); Tushant Mittal (University of Chicago); Youming Qiao (Center for Quantum Software and Information, University of Technology, Ultimo NSW 2007, Australia)
Efficient reconstruction of depth three arithmetic circuits with top fan-in two [paper, video]
Gaurav Sinha (Adobe Research India)
Monotone Complexity of Spanning Tree Polynomial Re-visited [paper, video]
Arkadev Chattopadhyay (TIFR); Rajit Datta (Goldman-Sachs); Utsab Ghosal (CMI); Partha Mukhopadhyay (Chennai Mathematical Institute)
Session 14.
11:30 AM - 12:30 PM EST
Chair: Eylon Yogev
*Room A*
On the download rate of homomorphic secret sharing [paper, video]
Ingerid Fosli (Stanford/Google); Yuval Ishai and Victor I. Kolobov (Technion); Mary Wootters (Stanford)
Small-Box Cryptography [paper, video]
Yevgeniy Dodis and Harish Karthikeyan (New York University); Daniel Wichs (Northeastern University)
Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions [paper, video]
Lijie Chen (MIT); Shuichi Hirahara (National Institute of Informatics); Neekon Vafa (MIT)
Beating Classical Impossibility of Position Verification [paper, video]
Jiahui Liu (University of Texas at Austin); Qipeng Liu (Simons Institute for the Theory of Computing); Luowen Qian (Boston University)
Indistinguishability Obfuscation of Null Quantum Circuits and Applications [paper, video]
James Bartusek (UC Berkeley); Giulio Malavolta (Max Planck Institute for Security and Privacy)
12:30 PM - 01:00 PM BREAK
Session 15.
01:00 PM - 02:00 PM EST
Chair: Rafael Oliveira
*Room B*
Time-Traveling Simulators Using Blockchains and Their Applications [paper, video]
Vipul Goyal (Carnegie Mellon University and NTT Research); Justin Raizes and Pratik Soni (Carnegie Mellon University)
Secret Sharing, Slice Formulas, and Monotone Real Circuits [paper, video]
Benny Applebaum (Tel-Aviv University); Amos Beimel (Ben Gurion University); Oded Nir and Naty Peter (Tel-Aviv University); Toniann Pitassi (University of Toronto, Columbia University, and IAS)
Small Hazard-Free Transducers [paper, video]
Johannes Bund and Christoph Lenzen (CISPA Helmholtz Center for Information Security); Moti Medina (Bar Ilan University)
What Does Dynamic Optimality Mean in External Memory? [paper, video]
Michael A. Bender (Stony Brook University); Martin Farach-Colton (Rutgers University); William Kuszmaul (MIT)
Support Recovery in Universal One-bit Compressed Sensing [paper, video]
Soumyabrata Pal (University of Massachusetts Amherst); Arya Mazumdar (University of California, San Diego)
Session 16.
02:00 PM - 03:00 PM EST
Chair: Raghuvansh R. Saxena
*Room A*
Keep That Card in Mind: Card Guessing with Limited Memory [paper, video]
Boaz Menuhin and Moni Naor (Weizmann Institue)
A Gaussian Fixed Point Random Walk [paper, video]
Yang P. Liu (Stanford University); Ashwin Sah and Mehtaab Sawhney (MIT) (Best Student Paper Award)
Geometric Bounds on the Fastest Mixing Markov Chain [paper, video]
Sam Olesker-Taylor and Luca Zanetti (University of Bath)
Balanced Allocations with Incomplete Information: The Power of Two Queries [paper, video]
Dimitrios Los and Thomas Sauerwald (University of Cambridge)
Domain Sparsification of Discrete Distributions using Entropic Independence [paper, video]
Nima Anari (Stanford University); Michal Derezinski (University of Michigan); Thuy-Duong Vuong (Stanford University); Elizabeth Yang (University of California, Berkeley)
03:00 PM - 03:30 PM BREAK
Session 17.
03:30 PM - 04:30 PM EST
Chair: Nicole Wein
*Room B*
A Unifying Framework for Characterizing and Computing Width Measures [paper, video]
Eduard Eiben (Royal Holloway, University of London, London, UK); Robert Ganian and Thekla Hamm (Algorithms and Complexity Group, TU Wien, Vienna, Austria); Lars Jaffke (Department of Informatics, University of Bergen, Bergen, Norway); O-joung Kwon (Department of Mathematics, Incheon National University, Incheon, South Korea)
Fixed-Parameter Sensitivity Oracles [paper, video]
Davide Bilò (University of Sassari); Katrin Casel (Hasso Plattner Institute, University of Potsdam); Keerti Choudhary (Indian Institute of Technology); Sarel Cohen, Tobias Friedrich, J. A. Gregor Lagodzinski, Martin Schirneck, and Simon Wietheger (Hasso Plattner Institute, University of Potsdam)
FPT Algorithms for Finding Near-Cliques in $c$-Closed Graphs [paper, video]
Balaram Behera (Georgia Tech); Edin Husić (London School of Economics and Political Science); Shweta Jain (University of Illinois, Urbana-Champaign); Tim Roughgarden (Columbia University); C. Seshadhri (University of California, Santa Cruz)
Vertex Fault-Tolerant Emulators [paper, video]
Greg Bodwin (University of Michigan); Michael Dinitz (Johns Hopkins University); Yasamin Nazari (University of Salzburg)
Correlation detection in trees for planted graph alignment [paper, video]
Luca Ganassali and Marc Lelarge (INRIA, DI/ENS, PSL Research University, Paris, France); Laurent Massoulié (MSR-Inria Joint Centre, INRIA, DI/ENS, PSL Research University, Paris, France.)
Session 18.
04:30 PM - 05:30 PM EST
Chair: Xue Chen
*Room A*
Probing to minimize [paper, video]
Weina Wang, Anupam Gupta, and Jalani Williams (Carnegie Mellon University)
Double Coverage with Machine-Learned Advice [paper, video]
Alexander Lindermayr and Nicole Megow (Department of Mathematics and Computer Science, University of Bremen, Germany.); Bertrand Simon (IN2P3 Computing Center, CNRS, Villeurbanne, France.)
Faster Sparse Matrix Inversion and Rank Computation in Finite Fields [paper, video]
Sílvia Casacuberta (Harvard University); Rasmus Kyng (ETH Zurich)
Uniform Bounds for Scheduling with Job Size Estimates [paper, video]
Ziv Scully and Isaac Grosof (Carnegie Mellon University); Michael Mitzenmacher (Harvard University)
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs [paper, video]
Farzam Ebrahimnejad, Ansh Nagda, and Shayan Oveis Gharan (University of Washington)

February 3rd

Session 19.
10:30 AM - 11:30 AM EST
Chair: Maryam Aliakbarpour
*Room A*
Testing Distributions of Huge Objects [paper, video]
Oded Goldreich (Weizmann Institute of Science); Dana Ron (Tel Aviv University)
Embeddings and labeling schemes for A* [paper, video]
Talya Eden and Piotr Indyk (MIT); Haike Xu (Tsinghua University)
Sublinear-Time Computation in the Presence of Online Erasures [paper, video]
Iden Kalemaj and Sofya Raskhodnikova (Boston University); Nithin Varma (Chennai Mathematical Institute)
On the Existence of Competitive Equilibrium with Chores [paper, video]
Bhaskar Ray Chaudhury (Max Planck Institute for Informatics); Jugal Garg, Peter McGlaughlin, and Ruta Mehta (University of Illinois at Urbana-Champaign)
More Dominantly Truthful Multi-task Peer Prediction with a Finite Number of Tasks [paper, video]
Yuqing Kong (Peking University)
Session 20.
11:30 AM - 12:30 PM EST
Chair: Alex Grilo
*Room B*
The importance of the spectral gap in estimating ground-state energies [paper, video]
Abhinav Deshpande and Alexey V. Gorshkov (University of Maryland); Bill Fefferman (University of Chicago)
Quantum Meets the Minimum Circuit Size Problem [paper, video]
Nai-Hui Chia (Indiana University Bloomington); Chi-Ning Chou (Harvard University); Jiayu Zhang (Boston University); Ruizhe Zhang (The University of Texas at Austin)
Interactive Proofs for Synthesizing Quantum States and Unitaries [paper, video]
Gregory Rosenthal (University of Toronto); Henry Yuen (Columbia University)
On polynomially many queries to NP or QMA oracles [paper, video]
Dorian Rudolph (Paderborn University); Sevag Gharibian (Universität Paderborn)
Circuit lower bounds for low-energy states of quantum code Hamiltonians [paper, video]
Anurag Anshu and Chinmay Nirkhe (UC Berkeley)
12:30 PM - 01:00 PM BREAK
Session 21.
01:00 PM - 02:00 PM EST
Chair: Antonina Kolokolova
*Room A*
PCPs and Instance Compression from a Cryptographic Lens [paper, video]
Liron Bronfman and Ron Rothblum (Technion)
Sample-based Proofs of Proximity [paper, video]
Guy Goldberg and Guy Rothblum (Weizmann Institute of Science)
Extremely Deep Proofs [paper, video]
Noah Fleming and Toniann Pitassi (University of Toronto); Robert Robere (McGill University)
On Semi-Algebraic Proofs and Algorithms [paper, video]
Noah Fleming (University of Toronto); Mika Göös (EPFL); Stefan Grosser and Robert Robere (McGill University)
Lifting With Sunflowers [paper, video]
Ian Mertz (University of Toronto); Shachar Lovett (UCSD); Raghu Meka (UCLA); Toniann Pitassi (University of Toronto); Jiapeng Zhang (University of Southern California)
Session 22.
02:00 PM - 03:00 PM EST
Chair: Makrand Sinha
*Room B*
Mixing of 3-term progressions in Quasirandom Groups [paper, video]
Amey Bhangale (University of California, Riverside, USA); Prahladh Harsha (Tata Institute of Fundamental Research, Mumbai, India); Sourya Roy (University of California, Riverside, USA)
Mixing in non-quasirandom groups [paper, video]
W. T. Gowers (unaffiliated); Emanuele Viola (NEU)
Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs [paper, video]
Amey Bhangale (UC Riverside); Aleksa Stankovic (KTH Royal Institute of Technology)
Separating the NP-Hardness of the Grothendieck problem from the Little-Grothendieck problem [paper, video]
Vijay Bhattiprolu (IAS/Princeton); Euiwoong Lee (University of Michigan); Madhur Tulsiani (Toyota Technological Institute Chicago)
Convex Influences [paper, video]
Anindya De (University of Pennsylvania); Shivam Nadimpalli and Rocco Anthony Servedio (Columbia University)
03:00 PM - 03:30 PM BREAK
Session 23.
03:30 PM - 04:30 PM EST
Chair: Yuval Filmus
*Room A*
Explicit Abelian Lifts and Quantum LDPC Codes [paper, video]
Fernando Granha Jeronimo (Institute for Advanced Study); Tushant Mittal (University of Chicago); Ryan O'Donnell and Pedro Paredes (Carnegie Mellon University); Madhur Tulsiani (Toyota Technological Institute at Chicago)
Bounded indistinguishability for simple sources [paper, video]
Andrej Bogdanov and Krishnamoorthy Dinesh (Chinese University of Hong Kong); Yuval Filmus, Yuval Ishai, and Avi Kaplan (Technion); Akshayaram Srinivasan (Tata Institute of Fundamental Research)
Randomness Extraction from Somewhat Dependent Sources [paper, video]
Marshall Ball (NYU); Oded Goldreich (Weizmann Institute of Science); Tal Malkin (Columbia University)
The Space Complexity of Sampling [paper, video]
Eshan Chattopadhyay and Jesse Goodman (Cornell University); David Zuckerman (University of Texas at Austin)
Larger Corner-Free Sets from Combinatorial Degenerations [paper, video]
Matthias Christandl (University of Copenhagen); Omar Fawzi and Hoang Ta (ENS de Lyon); Jeroen Zuiddam (University of Amsterdam)
Session 24.
04:30 PM - 05:30 PM EST
Chair: Noga Ron-Zewi
*Room B*
Nonlinear Repair Schemes of Reed-Solomon Codes [paper, video]
Roni Con and Itzhak Tamo (Tel Aviv University)
Low-bandwidth recovery of linear functions of Reed-Solomon-encoded data [paper, video]
Noah Shutty and Mary Wootters (Stanford University)
Improved Decoding of Expander Codes [paper, video]
Xue Chen (University of Science and Technology of China); Kuan Cheng (Peking University); Xin Li (Johns Hopkins University); Minghui Ouyang (Peking University)
A Complete Linear Programming Hierarchy for Linear Codes [paper, video]
Leonardo Coregliano and Fernando Granha Jeronimo (Institute for Advanced Study); Chris Jones (University of Chicago)
Algebraic Restriction Codes and their Applications [paper, video]
Divesh Aggarwal (Centre for Quantum Technologies, NUS); Nico Döttling and Jesko Dujmovic (CISPA Helmholtz Center); Mohammad Hajiabadi (University of Waterloo); Giulio Malavolta (Max Planck Institute for Security and Privacy); Maciej Obremski (National University of Singapore)