Rocco A. Servedio

activity

20112026

most citedEfficient deterministic approximate counting for low-degree polynomial threshold functions

1 citations · 1 across the 16 of their papers we have counts for

collaborators

Showing 2024Show all

5 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…

cs.CC2024

Detecting Low-Degree Truncation

Anindya De, Huan Li, Shivam Nadimpalli +1

We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution $D$ over $R^{n}$ and a collection of data points in…