8 papers
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…
On testing the incentive compatibility of single-parameter allocation mechanisms
Jason Milionis, William Pires
This paper is the first work at the intersection of game theory and property testing, giving algorithms and lower bounds for efficiently testing whether an allocation mechanism is…
DNF formulas are efficiently testable with relative error
Xi Chen, William Pires, Toniann Pitassi +1
We give a poly-query algorithm for testing whether an unknown and arbitrary function is an -term DNF, in the challenging relative-error frame…
Differential privacy from axioms
Guy Blanc, William Pires, Toniann Pitassi
Differential privacy (DP) is the de facto notion of privacy both in theory and in practice. However, despite its popularity, DP imposes strict requirements which guard against stro…
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…
Relative-error unateness testing
Xi Chen, Diptaksho Palit, Kabir Peshawaria +3
The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [CDH+24][CPPS25a][CPPS25b] In this paper we consider th…
Testing Juntas and Junta Subclasses with Relative Error
Xi Chen, William Pires, Toniann Pitassi +1
This papers considers the junta testing problem in a recently introduced ``relative error'' variant of the standard Boolean function property testing model. In relative-error testi…
Relative-error testing of conjunctions and decision lists
Xi Chen, William Pires, Toniann Pitassi +1
We study the relative-error property testing model for Boolean functions that was recently introduced in the work of Chen et al. (SODA 2025). In relative-error testing, the testing…