CCC

Keyphrases

Publications

2023

Dorit Aharonov, Sandy Irani
Translationally Invariant Constraint Optimization Problems. CCC (2023)
Per Austrin, Kilian Risse
Sum-Of-Squares Lower Bounds for the Minimum Circuit Size Problem. CCC (2023)
Andris Ambainis, Aleksandrs Belovs
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree. CCC (2023)
Prerona Chatterjee, Pavel Hrubes
New Lower Bounds Against Homogeneous Non-Commutative Circuits. CCC (2023)
Vinayak M. Kumar
Tight Correlation Bounds for Circuits Between AC0 and TC0. CCC (2023)
Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley
Separation of the Factorization Norm and Randomized Communication Complexity. CCC (2023)
Prahladh Harsha, Tulasimohan Molli, Ashutosh Shankar
Criticality of AC⁰-Formulae. CCC (2023)
Tommaso d'Orsi, Luca Trevisan
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs. CCC (2023)
Dorna Abdolazimi, Shayan Oveis Gharan
An Improved Trickle down Theorem for Partite Complexes. CCC (2023)
Bruno Pasqualotto Cavalar, Igor C. Oliveira
Constant-Depth Circuits vs. Monotone Circuits. CCC (2023)
Gil Cohen, Itay Cohen
Spectral Expanding Expanders. CCC (2023)
Xi Chen, Yuhao Li, Mihalis Yannakakis
Reducing Tarski to Unique Tarski (In the Black-Box Model). CCC (2023)
Deepanshu Kush, Shubhangi Saraf
Near-Optimal Set-Multilinear Formula Lower Bounds. CCC (2023)
Lennart Bittel, Sevag Gharibian, Martin Kliesch
The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate. CCC (2023)
Abhibhav Garg, Rafael Oliveira, Shir Peleg, Akash Kumar Sengupta
Radical Sylvester-Gallai Theorem for Tuples of Quadratics. CCC (2023)
Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj
Border Complexity of Symbolic Determinant Under Rank One Restriction. CCC (2023)
Emanuele Viola
New Sampling Lower Bounds via the Separator. CCC (2023)
Ben Davis, Robert Robere
Colourful TFNP and Propositional Proofs. CCC (2023)
Anand Natarajan, Chinmay Nirkhe
A Distribution Testing Oracle Separating QMA and QCMA. CCC (2023)
Dean Doron, Roei Tell
Derandomization with Minimal Memory Footprint. CCC (2023)
Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, Yu-Ching Shen
On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation. CCC (2023)
Dmitriy Kunisky, Xifan Yu
A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph. CCC (2023)
Peter Ivanov, Liam Pavlovic, Emanuele Viola
On Correlation Bounds Against Polynomials. CCC (2023)
Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She
On the Algebraic Proof Complexity of Tensor Isomorphism. CCC (2023)
Shuichi Hirahara, Zhenjian Lu, Hanlin Ren
Bounded Relativization. CCC (2023)
Dieter van Melkebeek, Nicollas M. Sdroievski
Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols. CCC (2023)
Lunjia Hu, Inbal Livni Navon, Omer Reingold
Generative Models of Huge Objects. CCC (2023)
Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors. CCC (2023)
Halley Goldberg, Valentine Kabanets
Improved Learning from Kolmogorov Complexity. CCC (2023)
Front Matter, Table of Contents, Preface, Conference Organization. CCC (2023)
Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas
Towards Optimal Depth-Reductions for Algebraic Formulas. CCC (2023)
Yanyi Liu, Rafael Pass
Leakage-Resilient Hardness vs Randomness. CCC (2023)
Josh Alman, Jaroslaw Blasiok
Matrix Multiplication and Number on the Forehead Communication. CCC (2023)
Eshan Chattopadhyay, Jyun-Jie Liao
Hardness Against Linear Branching Programs and More. CCC (2023)
Rahul Santhanam
An Algorithmic Approach to Uniform Lower Bounds. CCC (2023)
Russell Impagliazzo, Sasank Mouli, Toniann Pitassi
Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields. CCC (2023)
Srinivasan Arunachalam, Uma Girish
Trade-Offs Between Entanglement and Communication. CCC (2023)

volume 264, 2023

38th Computational Complexity Conference, CCC 2023, July 17-20, 2023, Warwick, UK CCC 264 (2023)

2022

volume 234, 2022

37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA. CCC 234 (2022)