Abstract
In 2012, Allender made intriguing conjectures that complexity classes, such as NEXP and BPP, can be characterized in terms of reductions to Kolmogorov complexity. Based on the conjectures, he proposed an ambitious research program for understanding these complexity classes through the lens of Kolmogorov complexity.
In this talk, I survey progress on his conjectures and explain their impacts. I plan to explain:
1. Allender's conjectures are false unless EXP^NP = NEXP (ITCS'20, STOC'20).
2. On the other hand, SZK (statistical zero knowledge) can be characterized by randomized reductions to an approximation of Kolmogorov complexity (ITCS'23, joint work with Eric Allender and Harsha Tirumala).
3. The average-case complexity of PH can be characterized by the worst-case meta-complexity (FOCS'20).
4. NP is hard on average if UP is not in DTIME(2^{O(n / log n)}) (STOC'21).