CCC'26: Accepted Papers

1. Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH.
   Rishav Gupta, Bingkai Lin, Xin Zheng.
2. Derandomized Graph Sampling With Applications to Deterministic Parallel Basis Finding.
   Aaron Putterman, Salil Vadhan, Vadim Zaripov.
3. Improved Bounds on the Space Complexity of Circuit Evaluation.
   Yakov Shalunov.
4. Probabilistically Checking Quantum Proofs, with Interaction.
   Baocheng Sun, Thomas Vidick.
5. Condensing and Extracting Against Online Adversaries.
   Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco A. Servedio.
6. Improved Parallel Repetition for GHZ-Supported Games via Spreadness.
   Yang P. Liu, Shachar Lovett, Kunal Mittal.
7. The Log-Rank Conjecture: New Equivalent Formulations.
   Lianna Hambardzumyan, Shachar Lovett, Morgan Shirley.
8. Efficient adversaries.
   Erfan Khaniki, Jan Pich, Dmitry Sokolov.
9. Hardness of Computing Nondeterministic Kolmogorov Complexity.
   Jinqiao Hu, Zhenjian Lu, Igor Oliveira.
10. The Rate-Immediacy Barrier in Explicit Tree Code Constructions.
    Gil Cohen, Leonard Schulman, Piyush Srivastava.
11. Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?.
    Cornelius Brand, Radu Curticapean, Petteri Kaski, Baitian Li, Ian Orzel, Tim Seppelt, Jiaheng Wang.
12. Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions.
    Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, Yu-Ching Shen.
13. Resolution Width Lifts to Near-Quadratic-Depth Res(⊕) Size.
    Dmitry Itsykson, Vladimir Podolskii, Alexander Shekhovtsov.
14. A weak regularity lemma for polynomials.
    Guy Moshkovitz, Dora Woodruff.
15. Derandomised tensor product gap amplification for quantum Hamiltonians.
    Thiago Bergamaschi, Tony Metger, Thomas Vidick, Tina Zhang.
16. Constant-depth circuits for polynomial GCD over any characteristic.
    Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf.
17. Rank bounds and polynomial-time PIT for depth-4 circuits with bounded top fan-in and bottom fan-in bounded by 2.
    Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta, Nir Shalmon, Amir Shpilka.
18. Multiplicative Pseudorandom Generators For Nondeterministic Circuits.
    Alon Dermer, Ronen Shaltiel.
19. When Hilbert approximates: A Strong Nullstellensatz for Approximate Polynomial Satisfiability.
    Sanyam Agarwal, Sagnik Dutta, Anurag Pandey, Himanshu Shukla.
20. On Factorization of Sparse Polynomials of Bounded Individual Degree.
    Aminadav Chuyoon, Amir Shpilka.
21. Wide Replacement Products Meet Gray Codes: Toward Optimal Small-Bias Sets.
    Gil Cohen, Itay Cohen.
22. Multilinear Algebraic Branching Programs and the Min-Partition Rank Method.
    Théo Fabris, Nutan Limaye, Srikanth Srinivasan, Amir Yehudayoff.
23. Quantum–Classical Equivalence for AND-Functions.
    Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett.
24. All Polynomial Generators Preserve Distance with Mutual Correlated Agreement.
    Sarah Bordage, Alessandro Chiesa, Ziyi Guan, Ignacio Manzur.
25. Polynomial Identity Testing for Read-4 Arithmetic Formulas.
    Nimrod Kaplan, Amir Shpilka.
26. A Simple Sub-Polynomial Degree Coboundary Expander.
    Max Hopkins, Arka Ray.
27. Optimal Depth-Three Circuits for Inner Product.
    Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Navid Talebanfard.
28. Plethysm is in #BQP.
    Aram W. Harrow, Matthias Christandl, Greta Panova, Pietro M. Posta, Michael Walter.
29. Frontier Space-Time Algorithms Using Only Full Memory.
    Petr Chmel, Aditi Dudeja, Michal Koucký, Ian Mertz, Ninad Rajgopal.
30. Bounds for Hardness Condensation in the Query Model.
    Chandrima Kayal, Rajat Mittal, Sai Soumya Nalli, Manaswi Parashaar, Karthikeya Polisetty, Jayalal Sarma, Nitin Saurabh.
31. Optimal Proximity Gap for Folded Reed–Solomon Codes via Subspace Designs.
    Lenny Liu, Fernando Granha Jeronimo, Pranav Rajpal.
32. Optimal Testing of Reed-Muller Codes with an Online Adversary.
    Esty Kelman, Uri Meir, Kai Zhe Zheng.
33. Fixed-Parameter Degree Bounds and Complexity of the Orbit Closure Intersection Problem for Tensors.
    Rafael Oliveira, Levent Dogan, John Maar, Youming Qiao.
34. Multilinear Formula Lower Bounds for Sparse Determinants.
    Pruthvi Boyapati, Suryajith Chillara, Pratyush Vempati.
35. Quantum Advantage in Tolerant Junta Testing.
    Avishay Tal, Weiqiang Yuan.
36. Trace Hermitian codes have vanishing bias.
    Amnon Ta-Shma, Swastik Kopparty, Kedem Yakirevitch.
37. Asymptotic Rank Speedup Theorems, Revisited.
    Josh Alman, Baitian Li.
38. Separations Above TFNP From Sherali-Adams Lower Bounds.
    Noah Fleming, Anna Gal, Deniz Imrek, Christophe Marciot.
39. Non-Clifford Gates are Required for Long-Term Memory.
    Joel Rajakumar, Jon Nelson, Michael Gullans.
40. Faux Determinism.
    Shalev Ben-David, M. H. Ebtehaj.
41. Strong Inapproximability of Monotone Circuit Size and Hardness of Monotone Learning under Worst-case Assumptions.
    Bruno Cavalar, Susanna de Rezende, Matthew Gray, Rahul Santhanam.
42. Systematic Data Structure Lower Bounds via the Query-with-Sketch Model.
    Sumegha Garg, Songhua He, Periklis A. Papakonstantinou, Yuanzhi Li, Xin Yang.
43. Randomized separations in black-box TFNP.
    Fyodor Kiselyov.