Shivam Nadimpalli

activity

20202026

most citedOn the Pauli Spectrum of QAC0

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

collaborators

Showing 2024Show all

6 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

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators

Shivam Nadimpalli, Shyamal Patel

We give a non-adaptive algorithm that makes $2^{O ~ (k l o g (1/ ε_{2} - ε_{1}))}$ queries to a Boolean function $f : {\pm 1}^{n} \to {\pm 1}$ and d…

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…