3 papers
cs.GT2026
On the Complexity of Mixed Equilibria in First-Price Auctions with Correlated Priors
Mark Chen, Xi Chen, Hao Cui +2
We show that computing an approximate mixed Bayes-Nash equilibrium in a discrete first-price auction with correlated priors is PPAD-complete. The key intermediate step in our reduc…
math.CO2026
Multiple Distance Ramsey Bounds For Graphs in Euclidean Spaces
Ayşegül Kula, Mohamed Omar, Jonah Stockwell +1
For a finite set and a finite graph , let be the minimum number of colors required to color while avoiding a mon…
cs.CC2025
Boolean function monotonicity testing requires (almost) queries
Mark Chen, Xi Chen, Hao Cui +2
We show that for any constant , any (two-sided error) adaptive algorithm for testing monotonicity of Boolean functions must have query complexity . This improves…