22 citations · 115 across the 31 of their papers we have counts for
6 papers · 1 filter
Boolean Unateness Testing with Adaptive Queries
Xi Chen, Erik Waingarten, Jinyu Xie
We give an adaptive algorithm which tests whether an unknown Boolean function is unate, i.e. every variable of is either non-decreasing or non-…
Sample-based high-dimensional convexity testing
Xi Chen, Adam Freilich, Rocco A. Servedio +1
In the problem of high-dimensional convexity testing, there is an unknown set which is promised to be either convex or -far from every conve…
Adaptivity is exponentially powerful for testing monotonicity of halfspaces
Xi Chen, Rocco A. Servedio, Li-Yang Tan +1
We give a -query adaptive algorithm for testing whether an unknown Boolean function , which is promised to be a halfspace, i…
Settling the query complexity of non-adaptive junta testing
Xi Chen, Rocco A. Servedio, Li-Yang Tan +2
We prove that any non-adaptive algorithm that tests whether an unknown Boolean function is a -junta or -far from every -junta must make $\widet…
On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer
Xi Chen, George Matikas, Dimitris Paparas +1
We show that the Revenue-Optimal Deterministic Mechanism Design problem for a single additive buyer is #P-hard, even when the distributions have support size 2 for each item and, m…
Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness
Xi Chen, Erik Waingarten, Jinyu Xie
We prove a lower bound of for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function $f:\{0,1\}^n\rightarrow…