71 citations · 437 across the 49 of their papers we have counts for
4 papers · 1 filter
Subgraph Sparsification and Nearly Optimal Ultrasparsifiers
Alexandra Kolla, Yury Makarychev, Amin Saberi +1
We consider a variation of the spectral sparsification problem where we are required to keep a subgraph of the original graph. Formally, given a union of two weighted graphs an…
Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria
Xi Chen, Shang-Hua Teng
It is a common belief that computing a market equilibrium in Fisher's spending model is easier than computing a market equilibrium in Arrow-Debreu's exchange model. This belief is…
Reducibility Among Fractional Stability Problems
Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman +2
In this paper, we resolve the computational complexity of a number of outstanding open problems with practical applications. Here is the list of problems we show to be PPAD-complet…
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
Xi Chen, Decheng Dai, Ye Du +1
We prove that the problem of computing an Arrow-Debreu market equilibrium is PPAD-complete even when all traders use additively separable, piecewise-linear and concave utility func…