Computational Complexity Conference
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
Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar and Roshan Raj. Border Complexity of Symbolic Determinant under Rank One Restriction
Peter Ivanov, Liam Pavlovic and Emanuele Viola. On correlation bounds against polynomials
Nicola Galesi, Joshua Grochow, Toniann Pitassi and Adrian She. On the algebraic proof complexity of Tensor Isomorphism
Lunjia Hu, Inbal Livni Navon and Omer Reingold. Generative Models of Huge Objects
Shuichi Hirahara, Zhenjian Lu and Hanlin Ren. Bounded Relativization
Russell Impagliazzo, Sasank Mouli and Toniann Pitassi. Lower bounds for Polynomial Calculus with extension variables over finite fields
Gil Cohen and Itay Cohen. Spectral Expanding Expanders
Eshan Chattopadhyay and Jyun-Jie Liao. Hardness against Linear Branching Programs and More
Dorna Abdolazimi and Shayan Oveis Gharan. An Improved Trickle-Down Theorem for Partite Complexes
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
Alex Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng and Minshen Zhu. On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors
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
Dieter van Melkebeek and Nicollas Mocelin Sdroievski. Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols
Vinayak Kumar. Tight Correlation Bounds for Circuits Between AC0 and TC0
Prahladh Harsha, Tulasimohan Molli and Ashutosh Shankar. Criticality of AC^0-Formulae
Abhibhav Garg, Rafael Mendes de Oliveira, Shir Peleg and Akash Kumar Sengupta. Radical Sylvester-Gallai Theorem for Tuples of Quadratics
Xi Chen, Yuhao Li and Mihalis Yannakakis. Reducing Tarski to Unique Tarski (in the Black-box Model)
Anand Natarajan and Chinmay Nirkhe. A randomized classical oracle separating QMA and QCMA
Dorit Aharonov and Sandy Irani. Translationally Invariant Constraint Optimization Problems
Andris Ambainis and Aleksandrs Belovs. An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
Uma Girish and Srinivasan Arunachalam. Trade-offs between Entanglement and Communication
Emanuele Viola. New sampling lower bounds via the separator
Tommaso d'Orsi and Luca Trevisan. A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs
Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan and Sébastien Tavenas. Towards Optimal Depth-Reductions for Algebraic Formulas
Bruno P. Cavalar and Igor C. Oliveira. Constant-Depth Circuits vs. Monotone Circuits
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
Yanyi Liu and Rafael Pass. Leakage-Resilient Hardness v.s. Randomness
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