68 citations · 163 across the 20 of their papers we have counts for
6 papers · 1 filter
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
Kyle Burke, Matthew Ferland, Shanghua Teng
We settle two long-standing complexity-theoretical questions-open since 1981 and 1993-in combinatorial game theory (CGT). We prove that the Grundy value (a.k.a. nim-value, or nimbe…
Transverse Wave: an impartial color-propagation game inspired by Social Influence and Quantum Nim
Kyle Burke, Matthew Ferland, Shanghua Teng
In this paper, we study a colorful, impartial combinatorial game played on a two-dimensional grid, Transverse Wave. We are drawn to this game because of its apparent simplicity, co…
Quantum Combinatorial Games: Structures and Computational Complexity
Kyle Burke, Matthew Ferland, Shang-Hua Teng
Recently, a standardized framework was proposed for introducing quantum-inspired moves in mathematical games with perfect information and no chance. The beauty of quantum games-suc…
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…
Computing Nash Equilibria: Approximation and Smoothed Complexity
Xi Chen, Xiaotie Deng, Shang-Hua Teng
We show that the BIMATRIX game does not have a fully polynomial-time approximation scheme, unless PPAD is in P. In other words, no algorithm with time polynomial in n and 1/εcan co…