Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More by Jin, Ce, Xu, Yinzhan

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

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

Learning Quantum Hamiltonians at Any Temperature in Polynomial Time by Bakshi, Ainesh, Liu, Allen, Moitra, Ankur, Tang, Ewin

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

AG Codes Achieve List Decoding Capacity over Constant-Sized Fields by Brakensiek, Joshua, Dhar, Manik, Gopi, Sivakanth, Zhang, Zihan

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

A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width by Gaitonde, Jason, Mossel, Elchanan

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

Near Optimal Alphabet-Soundness Tradeoff PCPs by Minzer, Dor, Zheng, Kai Zhe

“…Association for Computing Machinery STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing…”
Get full text

0-1 Knapsack in Nearly Quadratic Time by Jin, Ce

“…Association for Computing Machinery STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing…”
Get full text