Anindya De

activity

20132026

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

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

collaborators

Showing 2024Show all

5 papers · 1 filter

stat.ML2024

Sparsifying Suprema of Gaussian Processes

Anindya De, Shivam Nadimpalli, Ryan O'Donnell +1

We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let $T$ be any (possibly infinite) bounded set of vectors in $R^{n}$ , and l…

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