Publications de Alexandros Paul Hollender

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

The Frontier of Intractability for EFX with Two Agents

Alexandros Paul Hollender

We consider the problem of sharing a set of indivisible goods among agents in a fair manner, namely such that the allocation is envy-free up to any good (EFX). We focus on the problem of computing an EFX allocation in the two-agent case and characterize th ...

Springer International Publishing Ag2023

Envy-Free Cake-Cutting for Four Agents

Alexandros Paul Hollender

In the envy-free cake-cutting problem we are given a resource, usually called a cake and represented as the [0, 1] interval, and a set of n agents with heterogeneous preferences over pieces of the cake. The goal is to divide the cake among the n agents suc ...

Ieee Computer Soc2023

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