- 2023
- Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj:
Border Complexity of Symbolic Determinant Under Rank One Restriction. CCC 2023: 2:1-2:15 - Xi Chen, Yuhao Li, Mihalis Yannakakis:
Reducing Tarski to Unique Tarski (In the Black-Box Model). CCC 2023: 21:1-21:23 - Dorna Abdolazimi, Shayan Oveis Gharan:
An Improved Trickle down Theorem for Partite Complexes. CCC 2023: 10:1-10:16 - Dorit Aharonov, Sandy Irani:
Translationally Invariant Constraint Optimization Problems. CCC 2023: 23:1-23:15 - Josh Alman, Jaroslaw Blasiok
:
Matrix Multiplication and Number on the Forehead Communication. CCC 2023: 16:1-16:23 - Andris Ambainis, Aleksandrs Belovs:
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree. CCC 2023: 24:1-24:13 - Srinivasan Arunachalam, Uma Girish:
Trade-Offs Between Entanglement and Communication. CCC 2023: 25:1-25:23 - Per Austrin, Kilian Risse:
Sum-Of-Squares Lower Bounds for the Minimum Circuit Size Problem. CCC 2023: 31:1-31:21 - Lennart Bittel, Sevag Gharibian, Martin Kliesch:
The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate. CCC 2023: 34:1-34:24 - 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: 14:1-14:25 - Bruno Pasqualotto Cavalar
, Igor C. Oliveira:
Constant-Depth Circuits vs. Monotone Circuits. CCC 2023: 29:1-29:37 - Prerona Chatterjee
, Pavel Hrubes:
New Lower Bounds Against Homogeneous Non-Commutative Circuits. CCC 2023: 13:1-13:10 - Eshan Chattopadhyay, Jyun-Jie Liao:
Hardness Against Linear Branching Programs and More. CCC 2023: 9:1-9:27 - Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley:
Separation of the Factorization Norm and Randomized Communication Complexity. CCC 2023: 1:1-1:16 - 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: 33:1-33:45 - Gil Cohen, Itay Cohen:
Spectral Expanding Expanders. CCC 2023: 8:1-8:19 - Ben Davis, Robert Robere:
Colourful TFNP and Propositional Proofs. CCC 2023: 36:1-36:21 - Dean Doron
, Roei Tell:
Derandomization with Minimal Memory Footprint. CCC 2023: 11:1-11:15 - Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan
, Sébastien Tavenas:
Towards Optimal Depth-Reductions for Algebraic Formulas. CCC 2023: 28:1-28:19 - Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She:
On the Algebraic Proof Complexity of Tensor Isomorphism. CCC 2023: 4:1-4:40 - Abhibhav Garg, Rafael Oliveira, Shir Peleg, Akash Kumar Sengupta:
Radical Sylvester-Gallai Theorem for Tuples of Quadratics. CCC 2023: 20:1-20:30 - Halley Goldberg, Valentine Kabanets:
Improved Learning from Kolmogorov Complexity. CCC 2023: 12:1-12:29 - Prahladh Harsha, Tulasimohan Molli, Ashutosh Shankar:
Criticality of AC⁰-Formulae. CCC 2023: 19:1-19:24 - Shuichi Hirahara, Zhenjian Lu, Hanlin Ren
:
Bounded Relativization. CCC 2023: 6:1-6:45 - Lunjia Hu
, Inbal Livni Navon, Omer Reingold:
Generative Models of Huge Objects. CCC 2023: 5:1-5:20 - Russell Impagliazzo
, Sasank Mouli, Toniann Pitassi:
Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields. CCC 2023: 7:1-7:24 - Peter Ivanov, Liam Pavlovic, Emanuele Viola:
On Correlation Bounds Against Polynomials. CCC 2023: 3:1-3:35 - Vinayak M. Kumar
:
Tight Correlation Bounds for Circuits Between AC0 and TC0. CCC 2023: 18:1-18:40 - Dmitriy Kunisky, Xifan Yu:
A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph. CCC 2023: 30:1-30:25 - Deepanshu Kush, Shubhangi Saraf:
Near-Optimal Set-Multilinear Formula Lower Bounds. CCC 2023: 15:1-15:33