Person

Gilbert Théodore Maystre

This person is no longer with EPFL

Official source

https://people.epfl.ch/gilbert.maystre

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Official source

https://people.epfl.ch/gilbert.maystre

About this result

Related publications (11)

Please note that this is not a complete list of this person’s publications. It includes only semantically relevant works. For a full list, please refer to Infoscience.

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