Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes by First, Uriya A., Kaufman, Tali

“…ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing…”
Get full text

Lenzen’s Distributed Routing Generalized: A Full Characterization of Constant-Time Routability by Ghaffari, Mohsen, Wang, Brandon

“…ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing…”
Get full text

Generalized GM-MDS: Polynomial Codes Are Higher Order MDS by Brakensiek, Joshua, Dhar, Manik, Gopi, Sivakanth

“…ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing…”
Get full text

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques by Dalirrooyfard, Mina, Mathialagan, Surya, Williams, Virginia Vassilevska, Xu, Yinzhan

“…ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing…”
Get full text

Quantum State Obfuscation from Classical Oracles by Bartusek, James, Brakerski, Zvika, Vaikuntanathan, Vinod

“…ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing…”
Get full text

SNARGs under LWE via Propositional Proofs by Jin, Zhengzhong, Kalai, Yael, Lombardi, Alex, Vaikuntanathan, Vinod

“…ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing…”
Get full text

Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL by Doron, Dean, Pyne, Edward, Tell, Roei

“…ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing…”
Get full text

Beating Brute Force for Compression Problems by Hirahara, Shuichi, Ilango, Rahul, Williams, R. Ryan

“…ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing…”
Get full text

Local Geometry of NAE-SAT Solutions in the Condensation Regime by Sly, Allan, Sohn, Youngtak

“…ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing…”
Get full text

Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case Time by Ghaffari, Mohsen, Grunau, Christoph

“…ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing…”
Get full text

Improving the Bit Complexity of Communication for Distributed Convex Optimization by Ghadiri, Mehrdad, Lee, Yin Tat, Padmanabhan, Swati, Swartworth, William, Woodruff, David P., Ye, Guanghao

“…ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing…”
Get full text

New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with $\Omega(\sqrt{n}\log^k n)$ Distance by Kaufman, Tali, Tessler, Ran J.

“…ACM|Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing…”
Get full text

Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma by Chen, Lijie, Lyu, Xin

“…ACM|Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing…”
Get full text

Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW Is Not Zero-Knowledge) by Holmgren, Justin, Lombardi, Alex, Rothblum, Ron D.

“…ACM|Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing…”
Get full text

Simple and Fast Derandomization from Very Hard Functions: Eliminating Randomness at Almost No Cost by Chen, Lijie, Tell, Roei

“…ACM|Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing…”
Get full text

Adversarial Laws of Large Numbers and Optimal Regret in Online Classification by Alon, Noga, Ben-Eliezer, Omri, Dagan, Yuval, Moran, Shay, Naor, Moni, Yogev, Eylon

“…ACM|Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing…”
Get full text

Settling the Robust Learnability of Mixtures of Gaussians by Liu, Allen, Moitra, Ankur

“…ACM|Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing…”
Get full text

Robust Testing of Low Dimensional Functions by De, Anindya, Mossel, Elchanan, Neeman, Joe

“…ACM|Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing…”
Get full text

Sample-Efficient Proper PAC Learning with Approximate Differential Privacy by Ghazi, Badih, Golowich, Noah, Kumar, Ravi, Manurangsi, Pasin

“…ACM|Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing…”
Get full text

Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability by Chen, Lijie, Kol, Gillat, Paramonov, Dmitry, Saxena, Raghuvansh R., Song, Zhao, Yu, Huacheng

“…ACM|Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing…”
Get full text