25 citations · 80 across the 30 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2020★ 25 cited
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…
cs.CC2017
Consensus Halving is PPA-Complete
Aris Filos-Ratsikas, Paul W. Goldberg
We show that the computational problem CONSENSUS-HALVING is PPA-complete, the first PPA-completeness result for a problem whose definition does not involve an explicit circuit. We…
cs.CC2015
The Complexity of the Path-following Solutions of Two-dimensional Sperner/Brouwer Functions
Paul W. Goldberg
There are a number of results saying that for certain "path-following" algorithms that solve PPAD-complete problems, the solution obtained by the algorithm is PSPACE-complete to co…