Gilbert Maystre

STOC Conference 2025 Conference Paper

Supercritical Tradeoffs for Monotone Circuits

• Mika Göös
• Gilbert Maystre
• Kilian Risse
• Dmitry Sokolov 0001

ICLR Conference 2025 Conference Paper

The Complexity of Two-Team Polymatrix Games with Independent Adversaries

• Alexandros Hollender
• Gilbert Maystre
• Sai Ganesh Nagarajan

Adversarial multiplayer games are an important object of study in multiagent learning. In particular, polymatrix zero-sum games are a multiplayer setting where Nash equilibria are known to be efficiently computable. Towards understanding the limits of tractability in polymatrix games, we study the computation of Nash equilibria in such games where each pair of players plays either a zero-sum or a coordination game. We are particularly interested in the setting where players can be grouped into a small number of teams of identical interest. While the three-team version of the problem is known to be PPAD-complete, the complexity for two teams has remained open. Our main contribution is to prove that the two-team version remains hard, namely it is CLS-hard. Furthermore, we show that this lower bound is tight for the setting where one of the teams consists of multiple independent adversaries. On the way to obtaining our main result, we prove hardness of finding any stationary point in the simplest type of non-convex-concave min-max constrained optimization problem, namely for a class of bilinear polynomial objective functions.

FOCS Conference 2022 Conference Paper

Randomised Composition and Small-Bias Minimax

• Shalev Ben-David
• Eric Blais
• Mika Göös
• Gilbert Maystre

We prove 1 two results about randomised query complexity $\mathbf{R}(f)$. First, we introduce a linearised complexity measure LR and show that it satisfies an inner-optimal composition theorem: $\mathbf{R}(f^{\circ} g)\geq\Omega(\mathbf{R}(f)\mathbf{L R}(g))$ for all partial f and g, and moreover, LR is the largest possible measure with this property. In particular, LR can be polynomially larger than previous measures that satisfy an inner composition theorem, such as the max-conflict complexity of Gavinsky, Lee, Santha, and Sanyal (ICALP 2019). Our second result addresses a question of Yao (FOCS 1977). He asked if $\epsilon$-error expected query complexity $\overline{\mathbf{R}}_{\epsilon}(f)$ admits a distributional characterisation relative to some hard input distribution. Vereshchagin (TCS 1998) answered this question affirmatively in the bounded-error case. We show that an analogous theorem fails in the small-bias case $\epsilon=1/2-o(1)$. 1 This is an extended abstract. For the full version of this article, please refer to [BDBGM22].

FOCS Conference 2022 Conference Paper

Separations in Proof Complexity and TFNP

• Mika Göös
• Alexandros Hollender
• Siddhartha Jain 0002
• Gilbert Maystre
• William Pires
• Robert Robere
• Ran Tao 0013

It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show 1, however, that any such simulation needs to exploit huge coefficients: Resolution cannot be efficiently simulated by SA when the coefficients are written in unary. We also show that Reversible Resolution (a variant of MaxSAT Resolution) cannot be efficiently simulated by Nullstellensatz (NS). These results have consequences for total NP search problems. First, we characterise the classes PPADS, PPAD, SOPL by unary-SA, unary-NS, and Reversible Resolution, respectively. Second, we show that, relative to an oracle, PLS $\nsubseteq$ PPP, SOPL $\nsubseteq$ PPA, and EOPL $\nsubseteq$ UEOPL. In particular, together with prior work, this gives a complete picture of the black-box relationships between all classical TFNP classes introduced in the 1990s. 1 This is an extended abstract. For the full version of this article, please refer to [GHJ+22b].