2020-2021 Papers
This page contains links to some papers produced during the academic year of 2020-2021.
Theoretical Computer Science
- Abeer Al Ahmadieh and Cynthia Vinzant - Characterizing Principal Minors Of Symmetric Matrices Via Determinantal Multiaffine Polynomials
- Grant T. Barkley and Ricky Ini Liu - Channels, Billiards, and Perfect Matching 2-Divisibility
- Vijay Bhattiprolu, Euiwoong Lee, Assaf Naor - A Framework for Quadratic Form Maximization over Convex Sets through Nonconvex Relaxations
- Joshua Brakensiek, Sivakanth Gopi, Visu Makam - Lower Bounds for Maximally Recoverable Tensor Codes and Higher Order MDS Codes
- Peter Bürgisser, M. Levent Doğan, Visu Makam, Michael Walter, Avi Wigderson - Polynomial Time Algorithms in Invariant Theory for Torus Actions
- Justin Chen, Gregory Valiant, Paul Valiant - Worst-Case Analysis for Randomly Collected Data
- Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov - Automating Algebraic Proof Systems Is NP-Hard
- Harm Derksen and Visu Makam - Algorithms for orbit closure separation for
invariants and semi-invariants of matrices - Harm Derksen and Visu Makam - Polystability in Positive Characteristic And Degree Lower Bounds For Invariant Rings
- Asaf Ferber, Matthew Kwan, Lisa Sauermann - Singularity of sparse random matrices: simple proofs
- Asaf Ferber, Matthew Kwan, Lisa Sauermann - List-decodability with large radius for Reed–Solomon codes
- Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson - On the Power and Limitations of Branch and Cut
- Keith Frankston, Jeff Kahn, Jinyoung Park - On a Problem of M. Talagrand
- Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam - On the Pseudo-Deterministic Query Complexity of NP Search Problems
- David G. Harris, Fotis Iliopoulos, Vladimir Kolmogorov - A new notion of commutativity for the algorithmic Lovasz Local Lemma
- Hassan Hatam, Joseph Johnson, Ricky Ini Liu, Maria Macaulay - Determinantal Formulas For SEM Expansions Of Schubert Polynomials
- Fotis Iliopoulos and Ilias Zadik - Group testing and local search: is there a computational-statistical gap?
- Jeff Kahn, Bhargav Narayanan, Jinyoung Park - The Threshold For The Square Of A Hamilton Cycle
- Steven Klee, Bhargav Narayanan, Lisa Sauermann - Sharp Estimates for Spanning Trees
- Siddharth Krishna and Visu Makam - On The Tensor Rank Of The 3 X 3 Permanent And Determinant
- Matthew Kwan and Lisa Sauermann - On the permanent of a random symmetric matrix
- Jasper C.H. Lee and Paul Valiant - Optimal Sub-Gaussian Mean Estimation in R
- Jasper C.H. Lee and Paul Valiant - Uncertainty about Uncertainty: Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins
- Ricky Ini Liu and Christian Smith - Up- And Down- Operators On Young's Lattice
- Visu Makam and Avi Wigderson - Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties
- Jinyoung Park - Note on the Number Of Balanced Independent Sets In The Hamming Cube
- Zvi Rosen, Georgy Scholten, Cynthia Vinzant - Sparse Moments of Univariate Step Functions and Allele Frequency Spectra
- Lisa Sauermann and Yuval Wigderson - Polynomials that vanish to high order on most of the hypercube
- Lisa Sauermann - Finding solutions with distinct variables to systems of linear
equations over Fp - Faye Pasley Simon and Cynthia Vinzant - Invariant Hyperbolic Curves: Determinantal Representations and Applications to the Numerical Range
- Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir - Size and Depth Separation in Approximating Benign Functions with Neural Networks
- Or Zamir - Breaking the 2n barrier for 5-coloring and 6-coloring