5 citations · 12 across the 11 of their papers we have counts for
5 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…
Multi-Agent Systems for Computational Economics and Finance
Michael Kampouridis, Panagiotis Kanellopoulos, Maria Kyropoulou +2
In this article we survey the main research topics of our group at the University of Essex. Our research interests lie at the intersection of theoretical computer science, artifici…
Tight Inapproximability for Graphical Games
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
We provide a complete characterization for the computational complexity of finding approximate equilibria in two-action graphical games. We consider the two most well-studied appro…
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…