5 citations · 13 across the 19 of their papers we have counts for
7 papers · 1 filter
The Complexity of Gradient Descent: CLS = PPAD PLS
John Fearnley, Paul W. Goldberg, Alexandros Hollender +1
We study search problems that can be solved by performing Gradient Descent on a bounded convex polytopal domain and show that this class is equal to the intersection of two well-kn…
Consensus Halving for Sets of Items
Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi +2
Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work has shown that when the resource is represen…
Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents
Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros Hollender
We consider the -Consensus-Halving problem, in which a set of heterogeneous agents aim at dividing a continuous resource into two (not necessarily contiguous) portions…
Optimally Deceiving a Learning Leader in Stackelberg Games
Georgios Birmpas, Jiarui Gan, Alexandros Hollender +3
Recent results in the ML community have revealed that learning algorithms used to compute the optimal strategy for the leader to commit to in a Stackelberg game, are susceptible to…
A Topological Characterization of Modulo- Arguments and Implications for Necklace Splitting
Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki +1
The classes PPA- have attracted attention lately, because they are the main candidates for capturing the complexity of Necklace Splitting with thieves, for prime . Howeve…
Consensus-Halving: Does It Ever Get Easier?
Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki +1
In the -Consensus-Halving problem, a fundamental problem in fair division, there are agents with valuations over the interval , and the goal is to divide th…