25 citations · 80 across the 30 of their papers we have counts for
3 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…
Learning Strong Substitutes Demand via Queries
Paul W. Goldberg, Edwin Lock, Francisco Marmolejo-Cossío
This paper addresses the computational challenges of learning strong substitutes demand when given access to a demand (or valuation) oracle. Strong substitutes demand generalises t…