9 citations · 11 across the 5 of their papers we have counts for
6 papers
The Complexity of Exact and Approximate Nash Equilibria in Anonymous Games
Zhengyang Liu
We prove that, for every fixed rational , computing a -approximate Nash equilibrium in an -player two-strategy anonymous game is -complete. This ho…
Support Contraction for Well-Supported Nash Equilibria
Zhengyang Liu
We introduce the support contraction, a structural procedure for computing well-supported Nash equilibria (WSNE) in bimatrix games. On a common action rectangle, the procedure alte…
Settling the Complexity of Hylland--Zeckhauser Equilibria
Yonglei Yan, Yixin Tao, Zhengyang Liu
The Hylland--Zeckhauser (HZ) mechanism is a foundational framework for allocating indivisible goods in one-sided matching markets via lotteries supported by competitive prices and…
ACMo: Angle-Calibrated Moment Methods for Stochastic Optimization
Xunpeng Huang, Runxin Xu, Hao Zhou +3
Due to its simplicity and outstanding ability to generalize, stochastic gradient descent (SGD) is still the most widely used optimization method despite its slow convergence. Meanw…
SPAN: A Stochastic Projected Approximate Newton Method
Xunpeng Huang, Xianfeng Liang, Zhengyang Liu +4
Second-order optimization methods have desirable convergence properties. However, the exact Newton method requires expensive computation for the Hessian and its inverse. In this pa…
Distribution-free Junta Testing
Xi Chen, Zhengyang Liu, Rocco A. Servedio +2
We study the problem of testing whether an unknown -variable Boolean function is a -junta in the distribution-free property testing model, where the distance between function…