21 citations · 65 across the 25 of their papers we have counts for
5 papers · 1 filter
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…
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…
On the Hardness of Energy Minimisation for Crystal Structure Prediction
Duncan Adamson, Argyrios Deligkas, Vladimir Gusev +1
Crystal Structure Prediction (csp) is one of the central and most challenging problems in materials science and computational chemistry. In csp, the goal is to find a configuration…
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}…