Abstract: There are many theorems of the form "for all, there exists" (such as: all games have a Nash equilibrium, or all numbers have a prime factorisation). They have corresponding computational search problems (e.g. given a number, find a prime factorisation), and the word "total" refers to the property that all inputs have solutions, not just some of them. They include some important problems that do not seem to have polynomial-time algorithms, even though some of them are easy in practice. In the talk I give an overview of work on classifying their computational complexity. I will also mention some open problems.

Abstract: We discuss challenges at the interface of game theory and deep learning, motivated by multi-agent learning applications. Unlike single-agent learning settings where recent breakthroughs have been fueled, in part, by the success of gradient descent in computing approximate local minima of non-convex objectives, progress on the multi-agent deep learning front has been more challenging. Here, the role of single-objective optimization is played by equilibrium computation, but gradient-descent based methods have been less successful for this task, exhibiting unstable, oscillatory or divergent behavior. We discuss these challenges using a TFNP lens.

Abstract: Topological combinatorics abounds in existence results that can be turned into TFNP problems. I will present several intriguing results of this sort, whose corresponding TFNP problems have their complexity status still unsettled (as far as I know).

Abstract: We consider the query complexity of finding a local minimum of a function defined on a graph, where at most k rounds of interaction, aka adaptivity, with the oracle are allowed. Adaptivity is a fundamental concept studied due to the need to parallelize computation and understand the speedups attainable. The query complexity of local search is closely related to the complexity of computing stationary points of a function, thus bounds for local search can give insights into the performance of algorithms such as gradient descent.

We focus on the d-dimensional grid {1, 2, ..., n}^d, where the dimension d is a constant. We give algorithms and lower bounds that characterize the trade-off between the number of rounds of adaptivity and the query complexity of local search, when the number of rounds is constant and polynomial in n, respectively.

The local search analysis also enables us to characterize the query complexity of computing a Brouwer fixed point in rounds. Our proof technique for lower bounding the query complexity in rounds may be of independent interest as an alternative to the classical relational adversary method of Aaronson from the fully adaptive setting.

Based on joint work with Jiawei Li.

Abstract: We introduce a new technique for proving membership of problems in FIXP – the class capturing the complexity of computing a fixed-point of an algebraic circuit. Our technique constructs a “pseudogate” which can be used as a black box when building FIXP circuits. This pseudogate, which we term the “OPT-gate”, can solve most convex optimization problems. Using the OPT-gate, we prove new FIXP-membership results, and we generalize and simplify several known results from the literature on fair division, game theory and competitive markets. In particular, we prove complexity results for two classic problems: computing a market equilibrium in the Arrow-Debreu model with general concave utilities is in FIXP, and computing an envy-free division of a cake with general valuations is FIXP-complete. We further showcase the wide applicability of our technique, by using it to obtain simplified proofs and extensions of known FIXP-membership results for equilibrium computation for various types of strategic games, as well as the pseudomarket mechanism of Hylland and Zeckhauser.

Based on joint work with Aris Filos-Ratsikas, Kasper Høgh, and Alexandros Hollender.

Abstract: In light of the surprising result CLS = PLS ∩ PPAD by Fearnley et. al. (STOC'21), one may wonder whether further such collapses between TFNP subclasses are possible. In this talk, I will survey two recent sets of results regarding that question. The first establishes in an elementary black-box manner that the collapse progresses even further: it turns out that EOPL (a subclass of CLS) actually equals PLS ∩ PPAD too. A similar construction yields SOPL = PLS ∩ PPADS. The second investigates barriers to such collapses, i.e. ruling out black-box reductions. By characterising query-analogues of TFNP subclasses by proof systems, we show oracle separations between all classical TFNP subclasses, eventually completing the picture initiated by Beame et al. (JCSS'98). Those separations also extend to the newer class UEOPL (a subclass of EOPL), further showing that PLS ∩ PPAD does not reduce to UEOPL in a black-box fashion and “stopping” the collapse.

This is joint work with Mika Göös, Alexandros Hollender, Siddhartha Jain, William Pires, Robert Robere and Ran Tao.

Abstract: In this talk, I will survey the recent results that show cryptographic hardness of CLS⊆PPAD. Our focus will be more on the 'Fiat-Shamir' approach, which involves first designing an interactive protocol for an appropriate hard language and then turning it non-interactive using an appropriate hash function. In the end, I will briefly discuss our recent result which follows this approach to show CLS-hardness from *standard* hardness of iterated squaring and learning with errors. These hardness results can be extended to the class UEOPL⊆CLS.

(The talk is based on joint works with (i) Arka Rai Choudhuri, Pavel Hubáček, Krzysztof Pietrzak, Alon Rosen and Guy Rothblum, and (ii) Nir Bitansky, Arka Rai Choudhuri, Justin Holmgren, Alex Lombardi, Omer Paneth and Ron Rothblum.)

Abstract: Fair division is the problem of allocating a set of items among agents in a fair and efficient manner. This age-old problem, mentioned even in the Bible, arises naturally in a wide range of real-life settings, for example, school seat assignments, partnership dissolution, sharing of satellites, and dividing costs for climate resilience. Division based on competitive equilibrium (CE) has emerged as one of the best mechanisms for this problem. The existence and computability of CE have been extensively studied when all items are disposable goods, while the problem is less explored when some of them are non-disposable chores (bads). In this talk, I will discuss recent algorithmic advances on the computation of CE when each item may be a good, a chore, or both (mixed).

I will first consider the case of additive valuations, where when all items are goods, the CE set is well-known to be captured by convex programming formulations and thereby forms a convex set. In sharp contrast, with chores, the CE set may be nonconvex and disconnected. I will discuss how to handle this non-convexity through a new exterior-point method to find an approximate CE in polynomial time (FPTAS). This method seems general enough to work with any mathematical formulation that optimizes a coordinate-wise monotone function over linear constraints. Finally, I will discuss recent developments on the exchange setting (barter system) on existence and computational complexity.

Based on joint works with Shant Boodaghians, Bhaskar Ray Chaudhury, Jugal Garg, and Peter McGlaughlin.

Abstract: We consider the problem of computing a (pure) Bayes-Nash equilibrium in the first-price auction with continuous value distributions and discrete bidding space. We prove that when bidders have independent subjective prior beliefs about the value distributions of the other bidders, computing an ε-equilibrium of the auction is PPAD-complete, and computing an exact equilibrium is FIXP-complete.

Based on joint work with Aris Filos-Ratsikas, Alexandros Hollender, Philip Lazos, and Diogo Poças.

Abstract: In the ε-Consensus-Halving problem, we are given n probability measures v1,…,vn on the interval R=[0,1], and the goal is to partition R into two parts R+ and R− using at most n cuts, so that |vi(R+)−vi(R−)| ≤ ε for all i. This fundamental fair division problem was the first natural problem shown to be complete for the class PPA, and all subsequent PPA-completeness results for other natural problems have been obtained by reducing from it.

We show that ε-Consensus-Halving is PPA-complete even when the parameter ε is a constant. In fact, we prove that this holds for any constant ε < 1/5. As a result, we obtain constant inapproximability results for all known natural PPA-complete problems, including Necklace-Splitting, the Discrete-Ham-Sandwich problem, two variants of the pizza sharing problem, and for finding fair independent sets in cycles and paths.

Joint work with John Fearnley, Argyrios Deligkas, and Alexandros Hollender.

Abstract: We consider (i) the problem of finding a (possibly mixed) Nash equilibrium in congestion games, and (ii) the problem of finding an (exponential precision) fixed point of the gradient descent dynamics of a smooth function f: [0,1]^n→R. We prove that these problems are equivalent. Our result holds for various explicit descriptions of f, ranging from (almost general) arithmetic circuits, to degree-5 polynomials. By a very recent result of [Fearnley, Goldberg, Hollender, Savani '20] this implies that these problems are PPAD∩PLS-complete. As a corollary, we also obtain the following equivalence of complexity classes: CCLS = PPAD∩PLS.

Based on joint work with Yakov Babichenko.