We will meet in-person for a whole day of informal talks and discussions around computational complexity, and our plans for the future.

 Lunch and coffee will be provided. 

The meeting is scheduled for Wednesday, November 27th, at Imperial College London.  

How to get to Huxley Building: See google map 

How to get to room 218: When you enter the building, 218 is on your left (past an electronic door, across the big students' computer lab).

Note: Free for anyone to attend, but we are slightly limited in space. 

Program (may change a bit):

10:00 Gathering and coffee, cookies and a short introduction of participants 

10:30 Talk 1: Bruno Cavalar

11:00 Open problems session

12:00 Talk 2: Christian Ikenmeyer

12:30 Talk 3: Gaia Carenini

13:00 Lunch break

14:30 Talk 4: Jiaqi Lu

15:00 Talk 5: Erfan Khaniki

16:00 Coffee, cookies, plans, discussions and visions

17:00 End of meeting

Speakers:

Christian Ikenmeyer

We prove that in the algebraic metacomplexity framework, the decomposition of metapolynomials into their isotypic components can be implemented efficiently, namely with only a quasipolynomial blowup in the circuit size. This means that many existing algebraic complexity lower bound proofs can be efficiently converted into isotypic lower bound proofs via highest weight metapolynomials, a notion studied in geometric complexity theory. In the context of algebraic natural proofs, our result means that without loss of generality algebraic natural proofs can be assumed to be isotypic. Our proof is built on the Poincaré--Birkhoff--Witt theorem for Lie algebras and on Gelfand--Tsetlin theory, for which we give the necessary comprehensive background. 

Bruno Cavalar

We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribution of binary strings over which it is hard to approximate Kolmogorov complexity. Therefore, we characterize one-way puzzles by the average-case hardness of a uncomputable problem. This brings to the quantum setting a recent line of work that characterizes classical cryptography with the average-case hardness of a meta-complexity problem, initiated by Liu and Pass. Moreover, since the average-case hardness of Kolmogorov complexity over classically polynomial-time samplable distributions characterizes one-way functions, this result poses one-way puzzles as a natural generalization of one-way functions to the quantum setting. Furthermore, our equivalence goes through probability estimation, giving us the additional equivalence that one-way puzzles exist if and only if there is a quantum samplable distribution over which probability estimation is hard. We also observe that the oracle worlds of defined by Kretschmer et. al. rule out any relativizing characterization of one-way puzzles by the hardness of a problem in NP or QMA, which means that it may not be possible with current techniques to characterize one-way puzzles with another meta-complexity problem. 

Jiaqi Lu

We show *unconditionally* that there is an explicit family of DNF formulas, believed to be tautologies, with no short AC^0[p]-Frege proofs. Our argument goes through algebraic proof complexity and diagonalisation. It adapts the approach suggested by Santhanam-Tzameret to the constant-depth setting, where the DNF formulas, denoted $\Phi_n$, express that the recent lower bounds of Limaye-Srinivasan-Tavenas and Forbes against constant-depth algebraic circuits computing the Permanent on $n$ by $n$ matrices do not admit short constant-depth algebraic proofs (over finite fields).  We then examine the formulas $\Phi_n$ to explore the conjecture that they are tautologies, and more broadly study the proof complexity and meta-mathematics of algebraic circuit lower bounds. (Joint work with Rahul Santhanam and Iddo Tzameret.)

Gaia Carenini

A significant issue in theoretical computer science is the construction of explicit unbalanced expander graphs with nearly optimal parameters. Although it has been elusive so far to come up with explicit constructions for these objects, it is simple to show that choosing the edge set at random will give a graph with essentially optimal parameters. A description of an ideal unbalanced expander that requires space proportionate to the larger vertex set in the bipartite graph may therefore be produced effectively and with very little chance of error. However, for applications that would require space proportionate to the smaller vertex set — if they had access to an explicit construction — storing a full description would be overkill. In this work, we provide a general construction for unbalanced expander graphs that decreases the size of the circuit employed for computing the neighborhood function of the graph and that lowers the randomness required while still optimizing the expander's parameters. Our work relies on the connection among unbalanced expander graphs and k-independent family of functions presented in Christiani, Pagh, and Thorup (STOC 2015).  

Erfan Khaniki

Jump operators, Interactive Proofs and Proof Complexity Generators 

Supported in part by: the ERC EPRICOT project.