5 citations · 12 across the 11 of their papers we have counts for
7 papers · 1 filter
On the Smoothed Complexity of Combinatorial Local Search
Yiannis Giannakopoulos, Alexander Grosz, Themistoklis Melissourgos
We propose a unifying framework for smoothed analysis of combinatorial local optimization problems, and show how a diverse selection of problems within the complexity class PLS can…
Pure-Circuit: Tight Inapproximability for PPAD
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
The current state-of-the-art methods for showing inapproximability in PPAD arise from the -Generalized-Circuit (-GCircuit) problem. Rubinstein (2018) show…
Constant Inapproximability for PPA
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
In the -Consensus-Halving problem, we are given probability measures on the interval , and the goal is to partition into two parts…
Pizza Sharing is PPA-hard
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos
We study the computational complexity of finding a solution for the straight-cut and square-cut pizza sharing problems. We show that computing an -approximate solution…
Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos +1
We study the problem of finding an exact solution to the consensus halving problem. While recent work has shown that the approximate version of this problem is PPA-complete, we sho…
Approximating the Existential Theory of the Reals
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos +1
The Existential Theory of the Reals (ETR) consists of existentially quantified Boolean formulas over equalities and inequalities of polynomial functions of variables in $\mathbb{R}…
Existence of Evolutionarily Stable Strategies Remains Hard to Decide for a Wide Range of Payoff Values
Themistoklis Melissourgos, Paul Spirakis
The concept of an evolutionarily stable strategy (ESS), introduced by Smith and Price, is a refinement of Nash equilibrium in 2-player symmetric games in order to explain counter-i…