The Iterative Win-Win Method, and Explicit Constructions (without) Using It

Explicit constructions of "random-like" objects play an important role in complexity theory and pseudorandomness. For many important objects such as prime numbers and rigid matrices, it remains elusive to find fast deterministic algorithms for constructing them unconditionally, despite the fact that these objects are abundant and can be easily found using randomness.

This lecture will focus on two recent results: (1) an infinitely-often pseudodeterministic construction for primes (and in fact any dense property in polynomial time); (2) a pseudodeterministic algorithm for the range avoidance problem with an NP oracle, which implies novel near-maximum circuit lower bounds. Previously, only subexponential-time algorithms are known for both explicit construction problems. The main theme underlying both results is a new iterative win-win method that improves upon previous win-win arguments and leads to polynomial time bounds.

The first half of the lecture will provide basic backgrounds of the iterative win-win method, offering a high-level introduction. The second half will elaborate on the result (2). If time permits, we will also explore the recent surprising improvement by Li (https://eccc.weizmann.ac.il/report/2023/156) that gets rid of the iterative win-win method and proves an almost-everywhere exponential-size circuit lower bound.

Based on joint works with Lijie Chen, Shuichi Hirahara, Zhenjian Lu, Igor Oliveira, and Rahul Santhanam. The results on circuit lower bounds and range avoidance are subsumed by the work of Zeyong Li.