This workshop:

• Recent attempts to develop systematic methods to solve families of explicit construction problems
• Hopefully, this workshop will make the techniques available to a larger audience! ☺

What is the hardest explicit construction?

Circuit lower bounds

Explicit constructions

Spoiler: circuit lower bounds

Applying insights from circuit lower bounds to explicit constructions?

…and back?!

Range Avoidance I: Introduction

• Oliver Korten (Columbia University)

Range avoidance: a total search problem capturing the complexity of various explicit construction problems!

What is the hardest explicit construction?

A study rooted from logic…

Derandomization vs range avoidance

Range avoidance for low-depth circuits

Range Avoidance II:�Algorithms and Lower Bounds

• Jiatu Li (Massachusetts Institute of Technology)

Algorithms:

Lower bounds: Range avoidance is not in poly-time!

(Technical note: assuming crypto, and only for “binary” range avoidance)

Lower bounds:

Another reason you might be interested in:

This is a separation between randomized and deterministic algorithms!

Iterative Win-win I:�Pseudodeterministic Construction of Primes

• Hanlin Ren (University of Oxford)

Easy for randomized algorithms

Widely open for deterministic algorithms

Hanlin’s talk: possible for pseudodeterministic algorithms (what’s this?)

(only on infinitely many input lengths)

Iterative Win-win II:�New Circuit Lower Bounds via Range Aoidance

• Lijie Chen (University of California, Berkeley)

Range avoidance

Iterative win-win

Complexity theorists’ win-win arguments had been suboptimal for four decades!

Complexity theorists’ win-win arguments had been suboptimal for four decades + 1 extra month (?)