Total Search Problems in TCS
Complexity, Cryptography, Combinatorics, and more

8:45-9:45 Paul W. Goldberg

Introduction to total search problems and their classification (slides)

This talk is aimed mainly at people who are fairly new to the topic of TFNP, search problems that have guaranteed solutions that once found, can be easily verified, but where the problem of finding a solution in the first place may be hard. These problems have been classified using a number of complexity subclasses, the more important of which are PPAD, PLS, PPP, and CLS, which is the intersection of PPAD and PLS. I will introduce these (with a focus on PPAD and PPA) and discuss the general topic of what other related complexity classes are out there.

9:45-10:45 Robert Robere

Total Search Problems, Logic, and Proof Complexity (slides)

Complementing the algorithmic approach to TFNP is a logical and proof theoretic approach. Formally, the totality of an NP search problem can be phrased by the first-order tautology ∀x ∃y R(x,y), where R is a polynomial-time computable predicate, and y is bounded to be at most polynomially longer than the length of x. It turns out that discovering algorithms for total NP search problems is closely linked to the efficient provability of this tautology in various proof systems. In particular, one can show that a total search problem A can be reduced to a total search problem B if and only if the totality of B implies the totality of A, and this implication is provable in a weak proof system. This connection has deep consequences: for example, it reduces the problem of proving black-box separations between TFNP classes to proving lower bounds in propositional proof complexity, which are much easier to handle. 

In this talk, we will introduce and survey these results and indicate some future directions of study.

8:45-9:25 Sevag Gharibian

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem (slides)

The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite the success of the theory at showing intractability of problems such as computing Brouwer fixed points and Nash equilibria, subclasses of TFNP remain arguably few and far between. In this work, we define two new subclasses of TFNP borne of the study of complex polynomial systems: Multi-homogeneous Systems (MHS) and Sparse Fundamental Theorem of Algebra (SFTA). The first of these is based on Bézout's theorem from algebraic geometry, marking the first TFNP subclass based on an algebraic geometric principle. At the heart of our study is the computational problem known as Quantum SAT (QSAT) with a System of Distinct Representatives (SDR), first studied by [Laumann, Läuchli, Moessner, Scardicchio, and Sondhi 2010]. Among other results, we show that QSAT with SDR is MHS-complete, thus giving not only the first link between quantum complexity theory and TFNP, but also the first TFNP problem whose classical variant (SAT with SDR) is easy but whose quantum variant is hard. We also show how to embed the roots of a sparse, high-degree, univariate polynomial into QSAT with SDR, obtaining that SFTA is contained in a zero-error version of MHS. We conjecture this construction also works in the low-error setting, which would imply SFTA is contained in MHS.

No background in quantum computing is assumed. Joint work with Marco Aldi (Virginia Commonwealth University, USA) and Dorian Rudolph (Paderborn University, Germany).

9:25-10:05 Daniel Mitropolsky

TFNP and Cryptography: An Interplanetary Tour of Impagliazzo's Worlds (slides)

The hardness of total search problems (search problems where every instance has a solution) appears inherently related to cryptography: we do not know how to base cryptography on hardness of an NP-complete problem, and TFNP is (most would believe) a non-complete subclass of NP. Another suggestive connection is that one-way functions and TFNP hardness are the two possible consequences of the existence of hard "promise true" search problems (those in which the sampler always outputs solvable instances). 

This talk will present a lay-of-the-land of the burgeoning field of TFNP-and-crypto. Our tour will be of an interplanetary nature, as we visit each of Impagliazzo's possible "worlds"; even though these planets are shrouded in atmospheric clouds that obscure their surface, in our fly-by we will see what is known about total hardness in each one. I hope to convince you that TFNP-crypto is interesting and possibly useful: it may be an avenue to find new assumptions for crypto, or to prove implications between crypto primitives and/or NP hardness-- that is, to conclude that some of the planets we thought we'd seen were not planets at all, but mirages.

10:05-10:45 Noah Stephens-Davidowitz

The more the merrier! On total coding and lattice problems and the complexity of finding multicollisions (slides)

We study several natural total search problems related to error-correcting codes (and lattices) and show that they are closely connected to a natural class of computational problems that correspond to finding multicollisions in sufficiently compressing functions.

8:45-9:25 Neil Thapen

How to fit large complexity classes into TFNP (slides)

Subclasses of TFNP are usually defined by specifying a complete problem, which is necessarily in TFNP, and including all problems many-one reducible to it. We study two notions of how a TFNP problem can be reducible to an object, such as a complexity class, outside TFNP. This gives rise to subclasses of TFNP which capture some properties of that outside object. We show that well-known subclasses can arise in this way, for example PPA from reducibility to parity P and PLS from reducibility to P^NP.

We study subclasses arising from PSPACE and the polynomial hierarchy, and show that they are characterized by the propositional proof systems Frege and constant-depth Frege, extending the known pairings between natural TFNP subclasses and proof systems.

We study approximate counting from this point of view, and look for a subclass of TFNP that gives a natural home to combinatorial principles such as Ramsey which can be proved using approximate counting. We relate this to the recently-studied Long choice and Short choice problems.

9:25-10:05 Oliver Korten

Connections Between Total Search, Circuit Lower Bounds and Derandomization (slides)

10:05-10:45 Yuhao Li

Metamathematics of Resolution Lower Bounds: A TFNP Perspective (slides)