2021-2022 Papers
This page contains links to some papers produced during the academic year of 2021-2022.
Theoretical Computer Science
- Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir - Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond
- Benny Applebaum, Amos Beimel, Ode Nir, Naty Peter, Toniann Pitassi - Secret Sharing, Slice Formulas, and Monotone Real Circuit
- Vijay Bhattiprolu, Euiwoong Lee, Assaf Naor - A Framework for Quadratic Form Maximization over Convex Sets through Nonconvex Relaxations
- Vijay Bhattiprolu, Euiwoong Lee, Madhur Tulsiani - Separating the NP-Hardness of the Grothendieck problem from the Little-Grothendieck problem
- Mark Braverman, Sumegha Garg, Or Zamir - Tight Space Complexity of the Coin Problem
- Matija Bucic, Nemanja Draganic, Benny Sudakov, Tuan Tran - Unavoidable Hypergraphs
- Matija Bucic, Jacob Fox, Benny Sudakov - Clique minors in graphs with a forbidden subgraph
- Matija Bucic, Daniel Korandi, Benny Sudakov - Covering graphs by monochromatic trees and Helly-type results for hypergraphs
- Yuansi Chen and Ronen Eldan - Localization schemes: A framework for proving mixing bounds for Markov chains
- Leonardo Coregliano - Left-cut-percolation and induced-Sidrenko bigraphs
- Leonardo Coregliano, Fernando Granha Jeronimo, Chris Jones - A Complete Linear Programming Hierarchy for Linear Codes
- Leonardo Coregliano and Alexander Razborov - Biregularity in Sidorenko's Conjecture
- Ronen Eldan, Guy Kindler, Noam Lifshitz, Dor Minzer - Isoperimetric Inequalities Made Simpler
- Noah Fleming, Toniann Pitassi, Robert Robere - Extremely Deep Proofs
- Michael Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson - Proof Complexity Lower Bounds from Algebraic Circuit Complexity
- Shafi Goldwasser, Michael Kim, Vinod Vaikuntanathan, Or Zamir - Planting Undetectable Backdoors
- Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam - On the Pseudo-Deterministic Query Complexity of NP Search Problems
- Oded Goldreich and Avi Wigderson - Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model
- Russell Impagliazzo, Rex Lei, Jessica Sorrell - Reproducibility in Learning
- Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani - Explicit Abelian Lifts and Quantum LDPC Codes
- Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang - Connections between graphs and matrix spaces
- Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang - Lifting with Sunflowers
- James Lucas, Mengye Ren, Irene Kameni, Toniann Pitassi, Richard Zemel - Theoretical bounds on estimation error for meta-learning
- Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan - Tradeoffs for small-depth Frege proofs
- Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir - Size and Depth Separation in Approximating Natural Functions with Neural Networks