CCC23 Accepted Papers
CCC23 Accepted Papers
Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini and Morgan Shirley.
Separation of the factorization norm and randomized communication complexity
Peter Ivanov, Liam Pavlovic and Emanuele Viola.
On correlation bounds against polynomials
Lunjia Hu,
Inbal Livni Navon and Omer Reingold.
Generative Models of Huge Objects
Shuichi Hirahara, Zhenjian Lu and Hanlin Ren.
Bounded Relativization
Gil Cohen and Itay Cohen.
Spectral Expanding Expanders
Dean Doron and Roei Tell.
Derandomization with Minimal Memory Footprint
Halley Goldberg and Valentine Kabanets.
Improved Learning from Kolmogorov Complexity
Prerona Chatterjee and
Pavel Hrubes.
New Lower Bounds against Homogeneous Non-Commutative Circuits
Deepanshu Kush and Shubhangi Saraf.
Near-Optimal Set-Multilinear Formula Lower Bounds
Josh Alman and
Jarosław Błasiok.
Matrix Multiplication and Number On the Forehead Communication
Vinayak Kumar.
Tight Correlation Bounds for Circuits Between AC0 and TC0
Andris Ambainis and
Aleksandrs Belovs.
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
Emanuele Viola.
New sampling lower bounds via the separator
Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan and Sébastien Tavenas.
Towards Optimal Depth-Reductions for Algebraic Formulas
Dmitriy Kunisky and
Xifan Yu.
A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
Per Austrin and Kilian Risse.
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem
Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin and Yu-Ching Shen.
On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation
Lennart Bittel,
Sevag Gharibian and
Martin Kliesch.
The optimal depth of variational quantum algorithms is QCMA-hard to approximate
Rahul Santhanam.
An Algorithmic Approach to Uniform Lower Bounds
Robert Robere and
Ben Davis.
On Coloured TFNP and Propositional Proof Systems