Publications de Gilbert Théodore Maystre

Direct Sums for Parity Decision Trees

Gilbert Théodore Maystre, Mika Tapani Göös, Weiqiang Yuan

Direct sum theorems state that the cost of solving k instances of a problem is at least Ω(k) times the cost of solving a single instance. We prove the first such results in the randomised parity decision tree model. We show that a direct sum theorem holds ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2025

Supercritical Tradeoffs for Monotone Circuits

Gilbert Théodore Maystre, Mika Tapani Göös

We exhibit a monotone function computable by a monotone circuit of quasipolynomial size such that any monotone circuit of polynomial depth requires exponential size. This is the first size–depth tradeoff result for monotone circuits in the so-called superc ...

ACM2025

The Power of Decision Trees for Composition and Search Problems

Gilbert Théodore Maystre

The unifying theme of this thesis are decision trees. Given a boolean function

f

and an input

x

, a decision tree computes the value

f(x)

by repeatedly querying bits of

x

. Our work is two-fold. On one hand, we investigate direct sums and other relat ...

EPFL2025

Generalised Linial-Nisan Conjecture Is False for DNFs

Gilbert Théodore Maystre, Mika Tapani Göös, Weiqiang Yuan

Aaronson (STOC 2010) conjectured that almost k-wise independence fools constant-depth circuits; he called this the generalised Linial-Nisan conjecture. Aaronson himself later found a counterexample for depth-3 circuits. We give here an improved counterexam ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2025

Separations in Proof Complexity and TFNP

Gilbert Théodore Maystre, Mika Tapani Göös

It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, however, that any such simulation needs to exploit huge coefficients: Resolution cannot be efficiently simulated by SA when the coefficients are wri ...

ASSOC COMPUTING MACHINERY2024

Further Collapses in TFNP

Gilbert Théodore Maystre, Ran Tao, Mika Tapani Göös, Siddhartha Jain, Alexandros Paul Hollender

We show EOPL = PLS \cap PsansP \sansP AD. Here the class EOPL consists of all total search problems that reduce to the END -OF -POTENTIAL -LINE problem, which was introduced in the works by Hub'acv \ek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 202 ...

Siam Publications2024

One-Way Functions vs. TFNP: Simpler and Improved

Gilbert Théodore Maystre, Mika Tapani Göös, Weiqiang Yuan

Simon (1998) proved that it is impossible to construct collision-resistant hash functions from one-way functions using a black-box reduction. It is conjectured more generally that one-way functions do not imply, via a black-box reduction, the hardness of a ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2024

Randomised Composition and Small-Bias Minimax

Gilbert Théodore Maystre, Mika Tapani Göös

ACM2022

Separations in Proof Complexity and TFNP

Gilbert Théodore Maystre, Ran Tao, Mika Tapani Göös, Siddhartha Jain, Alexandros Paul Hollender

ACM2022

Further Collapses in TFNP

Gilbert Théodore Maystre, Ran Tao, Mika Tapani Göös, Siddhartha Jain, Alexandros Paul Hollender

We show EOPL = PLS ∩ PPAD. Here the class EOPL consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubáček and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

A Majority Lemma for Randomised Query Complexity

Gilbert Théodore Maystre, Mika Tapani Göös

We show that computing the majority of n copies of a boolean function g has randomised query complexity R(Maj∘gⁿ) = Θ(n⋅R ̅_{1/n}(g)). In fact, we show that to obtain a similar result for any composed function f∘gⁿ, it suffices to prove a sufficiently stro ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021