Xi Chen

activity

20232026

collaborators

Showing 2024Show all

4 papers · 1 filter

cs.CC2024

Lower Bounds for Convexity Testing

Xi Chen, Anindya De, Shivam Nadimpalli +2

We consider the problem of testing whether an unknown and arbitrary set $S \subseteq R^{n}$ (given as a black-box membership oracle) is convex, versus $ε$ -far from…

cs.CC2024

Relative-error monotonicity testing

Xi Chen, Anindya De, Yizhi Huang +4

The standard model of Boolean function property testing is not well suited for testing $sparse$ functions which have few satisfying assignments, since every such function…

cs.DS2024

Trace reconstruction from local statistical queries

Xi Chen, Anindya De, Chin Ho Lee +1

The goal of trace reconstruction is to reconstruct an unknown $n$ -bit string $x$ given only independent random traces of $x$ , where a random trace of $x$ is obtained by passing $x$ …

cs.DS2024

Testing Sumsets is Hard

Xi Chen, Shivam Nadimpalli, Tim Randolph +2

A subset $S$ of the Boolean hypercube $F_{2}^{n}$ is a sumset if $S = {a + b : a, b \in A}$ for some $A \subseteq F_{2}^{n}$ . Sumsets are central objects of study in add…