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

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. 

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

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).

Recent Related Work

Organizers

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