Computational Complexity Conference

CCC'23 Program

Schedule The slots for contributed talks are 30 minutes (including 5 minutes for questions and changing speakers). In addition there are invited talks on Monday, Wednesday and Thursday which are one hour each. The business meeting and conference reception are on Monday evening. We will have an excursion to Warwick Castle on Tuesday afternoon, followed by the conference dinner at Coombe Abbey in Coventry (private buses have been arranged for commuting to and from the Castle and dinner). We also have a rump session (where you can discuss your favorite open problems!) on Wednesday evening. All the talks and the business meeting will be held in the lecture theatre MS.01 (see interactive campus map), located inside the Zeeman building which houses the Warwick Mathematics Institute. The reception will be held in the atrium of the Zeeman building. Lunch will be at the Radcliffe conference centre.

All times below are in British Summer Time (BST) which is GMT+1.

Proceedings: The official version will be openly accessible via LIPIcs.

Monday, July 17

8:30	Registration and coffee
9:20	Opening remarks
9:30	Tight Correlation Bounds for Circuits Between AC0 and TC0 Vinayak Kumar
10:00	Constant-Depth Circuits vs. Monotone Circuits Bruno P. Cavalar and Igor C. Oliveira
10:30	Towards Optimal Depth-Reductions for Algebraic Formulas Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan and Sébastien Tavenas
11:00	Criticality of AC0-Formulae Prahladh Harsha, Tulasimohan Molli and Ashutosh Shankar
11:30-12:00	Coffee break
12:00	Invited talk: Meta-complexity and average-case complexity (abstract) Shuichi Hirahara Meta-complexity refers to the complexity of problems that ask about complexity. Recently, the notion of meta-complexity played important roles in making progress on fundamental open questions about average-case complexity and cryptography. In this talk, I will describe recent meta-computational approaches towards understanding average-case complexity.
13:00-14:30	Lunch at Radcliffe
14:30	Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols Dieter van Melkebeek and Nicollas Mocelin Sdroievski
15:00	Improved Learning from Kolmogorov Complexity Halley Goldberg and Valentine Kabanets
15:30	Leakage-Resilient Hardness Vs. Randomness Yanyi Liu and Rafael Pass
16:00-16:30	Coffee break
16:30	On the algebraic proof complexity of Tensor Isomorphism Nicola Galesi, Joshua Grochow, Toniann Pitassi and Adrian She
17:00	Lower bounds for Polynomial Calculus with extension variables over finite fields Russell Impagliazzo, Sasank Mouli and Toniann Pitassi
17:30	On Coloured TFNP and Propositional Proof Systems Robert Robere and Ben Davis
18:00	Reducing Tarski to Unique Tarski (in the Black-box Model) Xi Chen, Yuhao Li and Mihalis Yannakakis
18:30-20:30	Conference reception + Business meeting over wine and cheese

Tuesday, July 18

8:30	Coffee
9:30	Matrix Multiplication and Number On the Forehead Communication Josh Alman and Jarosław Błasiok
10:00	Separation of the factorization norm and randomized communication complexity Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini and Morgan Shirley
10:30-10:45	Short Coffee Break
10:45	Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem Per Austrin and Kilian Risse
11:15	A degree 4 sum-of-squares lower bound for the clique number of the Paley graph Dmitriy Kunisky and Xifan Yu
12:00-13:00	Lunch at Radcliffe
13:15	Excursion to Warwick Castle (leave from campus by bus at 13:15 to arrive at Warwick Castle at 14:00)
18:00	Conference dinner at Coombe Abbey in Coventry (leave from Warwick by bus at ~17:00 to reach Coombe Abbey by 17:30-18:00)

Wednesday, July 19

8:30	Coffee
9:30	Generative Models of Huge Objects Lunjia Hu, Inbal Livni Navon and Omer Reingold
10:00	An Improved Trickle-Down Theorem for Partite Complexes Dorna Abdolazimi and Shayan Oveis Gharan
10:30	Spectral Expanding Expanders Gil Cohen and Itay Cohen
11:00	Radical Sylvester-Gallai Theorem for Tuples of Quadratics Abhibhav Garg, Rafael Mendes de Oliveira, Shir Peleg and Akash Kumar Sengupta
11:30-12:00	Coffee Break
12:00	Invited talk: Spectral Graph Theory for Derandomizing Logspace (abstract) Salil Vadhan I will survey how tools from algorithmic spectral graph theory have enabled a number of recent advances in the derandomization of space-bounded computation, such as the derandomization of BPL in space o(log^{3/2} n), near-optimal derandomizations of ordered branching programs that are regular or of "medium width", and improved pseudorandom generators and/or weighted pseudorandom generators for permutation programs and general ordered branching programs.
13:00-14:30	Lunch at Radcliffe
14:30	Derandomization with Minimal Memory Footprint Dean Doron and Roei Tell
15:00	Hardness against Linear Branching Programs and More Eshan Chattopadhyay and Jyun-Jie Liao
15:30	On correlation bounds against polynomials Peter Ivanov, Liam Pavlovic and Emanuele Viola
16:00-16:30	Coffee break
16:30	Near-Optimal Set-Multilinear Formula Lower Bounds Deepanshu Kush and Shubhangi Saraf
17:00	New Lower Bounds against Homogeneous Non-Commutative Circuits Prerona Chatterjee and Pavel Hrubes
17:30	Border Complexity of Symbolic Determinant under Rank One Restriction Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar and Roshan Raj
18:00-19:00	Rump Session

Thursday, July 20

8:30	Coffee
9:30	On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors Alex Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng and Minshen Zhu
10:00	An algorithmic approach to uniform lower bounds Rahul Santhanam
10:30	Bounded Relativization Shuichi Hirahara, Zhenjian Lu and Hanlin Ren
11:00	New sampling lower bounds via the separator Emanuele Viola
11:30-12:00	Coffee break
12:00	Invited talk: NLTS Hamiltonians from good quantum codes (abstract) Nikolas Breuckmann The NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings [2014] posits that there exist families of Hamiltonians with all low energy states of non-trivial complexity (with complexity measured by the quantum circuit depth preparing the state). We prove this conjecture by showing that families of constant-rate and linear-distance QLDPC codes correspond to NLTS local Hamiltonians.
13:00-14:30	Lunch at Scarman
14:30	A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs Tommaso d'Orsi and Luca Trevisan
15:00	Translationally Invariant Constraint Optimization Problems Dorit Aharonov and Sandy Irani
15:30-16:00	Coffee break
16:00	A randomized classical oracle separating QMA and QCMA Anand Natarajan and Chinmay Nirkhe
16:30	The optimal depth of variational quantum algorithms is QCMA-hard to approximate Lennart Bittel, Sevag Gharibian and Martin Kliesch
17:00	An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree Andris Ambainis and Aleksandrs Belovs
17:30-18:00	Coffee break
18:00	Trade-offs between Entanglement and Communication Uma Girish and Srinivasan Arunachalam
18:30	On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin and Yu-Ching Shen
19:00	Closing remarks
-	Boxed dinner (provided)