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:30Registration and coffee
9:20Opening remarks
Tight Correlation Bounds for Circuits Between AC0 and TC0

Vinayak Kumar

Constant-Depth Circuits vs. Monotone Circuits

Bruno P. Cavalar and Igor C. Oliveira

Towards Optimal Depth-Reductions for Algebraic Formulas

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan and Sébastien Tavenas

Criticality of AC0-Formulae

Prahladh Harsha, Tulasimohan Molli and Ashutosh Shankar

11:30-12:00Coffee break
Invited talk: Meta-complexity and average-case complexity (abstract)

Shuichi Hirahara

13:00-14:30Lunch at Radcliffe
14:30 Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols

Dieter van Melkebeek and Nicollas Mocelin Sdroievski

Improved Learning from Kolmogorov Complexity

Halley Goldberg and Valentine Kabanets

Leakage-Resilient Hardness Vs. Randomness

Yanyi Liu and Rafael Pass

16:00-16:30Coffee break
On the algebraic proof complexity of Tensor Isomorphism

Nicola Galesi, Joshua Grochow, Toniann Pitassi and Adrian She

Lower bounds for Polynomial Calculus with extension variables over finite fields

Russell Impagliazzo, Sasank Mouli and Toniann Pitassi

On Coloured TFNP and Propositional Proof Systems

Robert Robere and Ben Davis

Reducing Tarski to Unique Tarski (in the Black-box Model)

Xi Chen, Yuhao Li and Mihalis Yannakakis

18:30-20:30Conference reception + Business meeting over wine and cheese

Tuesday, July 18

Matrix Multiplication and Number On the Forehead Communication

Josh Alman and Jarosław Błasiok

Separation of the factorization norm and randomized communication complexity

Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini and Morgan Shirley

10:30-10:45Short Coffee Break
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem

Per Austrin and Kilian Risse

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph

Dmitriy Kunisky and Xifan Yu

12:00-13:00Lunch at Radcliffe
13:15Excursion to Warwick Castle

(leave from campus by bus at 13:15 to arrive at Warwick Castle at 14:00)

18:00Conference 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

Generative Models of Huge Objects

Lunjia Hu, Inbal Livni Navon and Omer Reingold

An Improved Trickle-Down Theorem for Partite Complexes

Dorna Abdolazimi and Shayan Oveis Gharan

Spectral Expanding Expanders

Gil Cohen and Itay Cohen

Radical Sylvester-Gallai Theorem for Tuples of Quadratics

Abhibhav Garg, Rafael Mendes de Oliveira, Shir Peleg and Akash Kumar Sengupta

11:30-12:00Coffee Break
Invited talk: Spectral Graph Theory for Derandomizing Logspace (abstract)

Salil Vadhan

13:00-14:30Lunch at Radcliffe
Derandomization with Minimal Memory Footprint

Dean Doron and Roei Tell

Hardness against Linear Branching Programs and More

Eshan Chattopadhyay and Jyun-Jie Liao

On correlation bounds against polynomials

Peter Ivanov, Liam Pavlovic and Emanuele Viola

16:00-16:30Coffee break
Near-Optimal Set-Multilinear Formula Lower Bounds

Deepanshu Kush and Shubhangi Saraf

New Lower Bounds against Homogeneous Non-Commutative Circuits

Prerona Chatterjee and Pavel Hrubes

Border Complexity of Symbolic Determinant under Rank One Restriction

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar and Roshan Raj

18:00-19:00Rump Session

Thursday, July 20

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

An algorithmic approach to uniform lower bounds

Rahul Santhanam

Bounded Relativization

Shuichi Hirahara, Zhenjian Lu and Hanlin Ren

New sampling lower bounds via the separator

Emanuele Viola

11:30-12:00Coffee break
Invited talk: NLTS Hamiltonians from good quantum codes (abstract)

Nikolas Breuckmann

13:00-14:30Lunch at Scarman
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs

Tommaso d'Orsi and Luca Trevisan

Translationally Invariant Constraint Optimization Problems

Dorit Aharonov and Sandy Irani

15:30-16:00Coffee break
A randomized classical oracle separating QMA and QCMA

Anand Natarajan and Chinmay Nirkhe

The optimal depth of variational quantum algorithms is QCMA-hard to approximate

Lennart Bittel, Sevag Gharibian and Martin Kliesch

An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

Andris Ambainis and Aleksandrs Belovs

17:30-18:00Coffee break
Trade-offs between Entanglement and Communication

Uma Girish and Srinivasan Arunachalam

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)