Gilbert Théodore Maystre | EPFL Graph Search

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