14 citations · 14 across the 3 of their papers we have counts for
3 papers
cs.DM2025
Semi-Random Graphs, Robust Asymmetry, and Reconstruction
Julian Asilis, Xi Chen, Dutch Hansen +1
The Graph Reconstruction Conjecture famously posits that any undirected graph on at least three vertices is determined up to isomorphism by its family of (unlabeled) induced subgra…
cs.GT2009
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…
cs.CC2009★ 14 cited
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…