Zobrazeno 1 - 10
of 29
pro vyhledávání: '"Nadimpalli, Shivam"'
We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let $T$ be any (possibly infinite) bounded set of vectors in $\mathbb{R}^n$, and let $\{{\boldsymbol{X}}_t\}_{t\in T}$ be the canonical Gaussian process
Externí odkaz:
http://arxiv.org/abs/2411.14664
We consider the problem of testing whether an unknown and arbitrary set $S \subseteq \mathbb{R}^n$ (given as a black-box membership oracle) is convex, versus $\varepsilon$-far from every convex set, under the standard Gaussian distribution. The curre
Externí odkaz:
http://arxiv.org/abs/2410.17958
Autor:
Chen, Xi, De, Anindya, Huang, Yizhi, Li, Yuhao, Nadimpalli, Shivam, Servedio, Rocco A., Yang, Tianqi
The standard model of Boolean function property testing is not well suited for testing $\textit{sparse}$ functions which have few satisfying assignments, since every such function is close (in the usual Hamming distance metric) to the constant-0 func
Externí odkaz:
http://arxiv.org/abs/2410.09235
Autor:
Nadimpalli, Shivam
This thesis considers algorithmic and structural aspects of high-dimensional convex sets with respect to the standard Gaussian measure. Among our contributions, (i) we introduce a notion of "influence" for convex sets that yields the first quantitati
Autor:
Nadimpalli, Shivam, Patel, Shyamal
We give a non-adaptive algorithm that makes $2^{\tilde{O}(\sqrt{k\log(1/\varepsilon_2 - \varepsilon_1)})}$ queries to a Boolean function $f:\{\pm 1\}^n \rightarrow \{\pm 1\}$ and distinguishes between $f$ being $\varepsilon_1$-close to some $k$-junta
Externí odkaz:
http://arxiv.org/abs/2404.13502
We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution ${\cal D}$ over $\mathbb{R}^n$ and a collection of data points in $\mathbb{R}^n$, distinguish between the two possibilities that (i) the
Externí odkaz:
http://arxiv.org/abs/2402.08133
A subset $S$ of the Boolean hypercube $\mathbb{F}_2^n$ is a sumset if $S = \{a + b : a, b\in A\}$ for some $A \subseteq \mathbb{F}_2^n$. Sumsets are central objects of study in additive combinatorics, featuring in several influential results. We prov
Externí odkaz:
http://arxiv.org/abs/2401.07242
Inspired by the classic problem of Boolean function monotonicity testing, we investigate the testability of other well-studied properties of combinatorial finite set systems, specifically \emph{intersecting} families and \emph{union-closed} families.
Externí odkaz:
http://arxiv.org/abs/2311.11119
Publikováno v:
STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 1498-1506
The circuit class $\mathsf{QAC}^0$ was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower bounds against such circuits is a longstanding challenge in quantum c
Externí odkaz:
http://arxiv.org/abs/2311.09631
We study the approximability of general convex sets in $\mathbb{R}^n$ by intersections of halfspaces, where the approximation quality is measured with respect to the standard Gaussian distribution $N(0,I_n)$ and the complexity of an approximation is
Externí odkaz:
http://arxiv.org/abs/2311.08575