Publications de Gilbert Théodore Maystre

Direct Sums for Parity Decision Trees

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

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

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

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

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

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

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

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

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

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

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

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

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

ACM2022

Separations in Proof Complexity and TFNP

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

ACM2022

Further Collapses in TFNP

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

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