Recent Developments in
Explicit Constructions

Summary

There are many well-known combinatorial objects whose existence follows from a non-constructive probabilistic argument. These objects might be graphs (e.g., Ramsey graphs, expanders, extractors), sets or families of sets (e.g., error-correcting codes, designs), matrices (e.g., rigid matrices), and strings (e.g., truth tables of high circuit complexity). However, algorithmic applications of these objects often require explicit constructions. The standard meaning of "explicit" is that the object should be produced by a deterministic procedure running in polynomial time in the size of the object. The probabilistic method is inherently non-constructive and thus does not yield explicit constructions in this sense.

For a long time, the question of explicit constructions was typically studied in isolation for each different combinatorial object. In contrast, in the last three years, there has been growing interest in a more general theory of explicit constructions, focusing on finding explicit constructions for an entire class of problems rather than specific ones. This workshop will focus on this recent perspective, covering from the theory of range avoidance to the construction of canonical primes and hard truth tables.

The workshop will introduce these exciting developments to a general audience and highlight several directions for further research.

Schedule

Day 1

• Hanlin Ren (University of Oxford)
  Introduction: Recent Developments in Explicit Constructions  [slides]
  
  

• Oliver Korten (Columbia University)
  Range Avoidance (Part I): Introduction to Range Avoidance  [slides]

In this talk I will give a high-level introduction to Range Avoidance, a total search problem which has recently come into focus as a computational task capturing the complexity of various explicit construction problems. I will discuss the known upper/lower bounds on the complexity of range avoidance in general, reductions between range avoidance and explicit construction problems, and connections to classical questions in derandomization. Finally I will discuss a line of recent work studying Range Avoidance for low depth circuits. 

• Jiatu Li (Massachusetts Institute of Technology)
  Range Avoidance (Part 2): Algorithms and Lower Bounds  [slides]

Algorithms and lower bounds for the range avoidance problem play a pivotal role in offering a systematic lens through which to understand the complexity of concrete explicit construction problems. This talk will provide an overview of recent advancements in algorithms and lower bounds for range avoidance, along with their implications. We will explain the intuition behind an unconditional FP^NP algorithm for range avoidance of ACC^0 circuits and a hardness result for range avoidance based on cryptographic assumptions.

Day 2

• Hanlin Ren (University of Oxford)
  The Iterative Win-Win  Paradigm (Part I): Pseudodeterministic Construction of Primes  [slides]

A randomized algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser (2011) posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time.

We provide a positive solution to this question in the infinitely-often regime. In more detail, we give an unconditional polynomial-time randomized algorithm B such that, for infinitely many values of n, B(1^n) outputs a canonical n-bit prime p_n with high probability. More generally, we prove that for every dense property Q of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying Q. This improves upon a subexponential-time construction of Oliveira and Santhanam (2017).

Our construction uses several new ideas, including a novel bootstrapping technique for pseudodeterministic constructions, and a quantitative optimization of the uniform hardness-randomness framework of Chen and Tell (2021), using a variant of the Shaltiel-Umans generator (2005).

• Lijie Chen (University of California,  Berkeley)
  The Iterative Win-Win  Paradigm (Part 2): New Circuit Lower Bounds via Solving Range Avoidance  [slides]
  Almost all n-bit Boolean functions have near-maximum (2^n/n) circuit complexity, and a central challenge of complexity theory is to pinpoint one such hard function. Formally, the goal is to identify the smallest complexity class containing a language with exponential circuit complexity. Despite being extremely important, there had been essentially no progress on this question since the four-decade-old work of Kannan~\cite{kan82}. In particular, it remained open whether Sigma_2 E, an important frontier class in complexity theory, contains a language with exponential circuit complexity.
  
  In a recent paper with Hanlin Ren and Shuichi Hirahara ([CHR'23]), we finally resolved this long-standing open question by showing that Sigma_2 E requires near-maximum (2^n/n) circuit complexity. The lower bound also extends to S_2E/1 (symmetric exponential time with one bit of advice). Our lower bound was further simplified and improved by an exciting recent work by Zeyong Li [Li'23], who showed that S_2E (and therefore Sigma_2 E) requires a maximum circuit complexity on all input lengths.
  
  In this talk, I will explain the new lower bounds for Sigma_2 E, which are corollaries of new algorithms for range avoidance. In particular, I will first describe an algorithm for range avoidance (from [CHR'23]) that works on infinitely many input lengths (which follows the iterative win-win paradigm). I will then explain how [Li'23] significantly simplifies and improves the CHR'23 algorithm to work on all input lengths. This improvement also allows [Li'23] to answer a recent open question posed by Vyas and Williams, giving a quasi-polynomial-size depth-3 AC^0 circuits for the Missing String problem.

Recent Related Work

• The Hardest Explicit Construction (Oliver Korten) [FOCS'2021]

• On the Range Avoidance Problem for Circuits (Hanlin Ren, Rahul Santhanam, Zhikun Wang) [FOCS'2022]

• Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness (Venkatesan Guruswami, Xin Lyu, Xiuhan Wang) [RANDOM'2022]

• Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms (Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren) [STOC'2023]

• Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic (Rahul Ilango, Jiatu Li, Ryan Williams) [STOC'2023]

• Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms (Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi) [RANDOM'2023]

• On Oracles and Algorithmic Methods for Proving Lower Bounds (Nikhil Vyas, Ryan Williams) [ITCS' 2023]

• Polynomial-Time Pseudodeterministic Construction of Primes (Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam). [FOCS'2023]

• Symmetric Exponential Time Requires Near-Maximum Circuit Size (Lijie Chen, Shuichi Hirahara, Hanlin Ren) [Preprint]

• Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform (Zeyong Li) [Preprint]

Organizers

Please feel free to reach out to one of the organizers in case you have any questions or feedback about the workshop:

• Lijie Chen (University of California, Berkeley)

• Igor C. Oliveira (University of Warwick)

• Rahul Santhanam (University of Oxford)