Zobrazeno 1 - 10
of 124
pro vyhledávání: '"Narayanan, Shyam"'
Autor:
Narayanan, Shyam
Cluster analysis focuses on understanding the cluster structure of data, and is perhaps one of the most important subfields in high-dimensional data analysis. Traditionally, cluster analysis focuses on partitioning data into closely related groups, s
Externí odkaz:
https://hdl.handle.net/1721.1/156617
Suppose we have a memory storing $0$s and $1$s and we want to estimate the frequency of $1$s by sampling. We want to do this I/O-efficiently, exploiting that each read gives a block of $B$ bits at unit cost; not just one bit. If the input consists of
Externí odkaz:
http://arxiv.org/abs/2410.14643
Autor:
Narayanan, Shyam
We give an improved algorithm for learning a quantum Hamiltonian given copies of its Gibbs state, that can succeed at any temperature. Specifically, we improve over the work of Bakshi, Liu, Moitra, and Tang [BLMT24], by reducing the sample complexity
Externí odkaz:
http://arxiv.org/abs/2407.04540
Autor:
Narayanan, Shyam
We provide optimal lower bounds for two well-known parameter estimation (also known as statistical estimation) tasks in high dimensions with approximate differential privacy. First, we prove that for any $\alpha \le O(1)$, estimating the covariance o
Externí odkaz:
http://arxiv.org/abs/2310.06289
Autor:
Narayanan, Shyam, Cartiglia, Matteo, Rubino, Arianna, Lego, Charles, Frenkel, Charlotte, Indiveri, Giacomo
Low-power event-based analog front-ends (AFE) are a crucial component required to build efficient end-to-end neuromorphic processing systems for edge computing. Although several neuromorphic chips have been developed for implementing spiking neural n
Externí odkaz:
http://arxiv.org/abs/2309.03221
We study the classic Euclidean Minimum Spanning Tree (MST) problem in the Massively Parallel Computation (MPC) model. Given a set $X \subset \mathbb{R}^d$ of $n$ points, the goal is to produce a spanning tree for $X$ with weight within a small factor
Externí odkaz:
http://arxiv.org/abs/2308.00503
Autor:
Chen, Sitan, Narayanan, Shyam
We revisit the well-studied problem of learning a linear combination of $k$ ReLU activations given labeled examples drawn from the standard $d$-dimensional Gaussian measure. Chen et al. [CDG+23] recently gave the first algorithm for this problem to r
Externí odkaz:
http://arxiv.org/abs/2307.12496
We consider the question of Gaussian mean testing, a fundamental task in high-dimensional distribution testing and signal processing, subject to adversarial corruptions of the samples. We focus on the relative power of different adversaries, and show
Externí odkaz:
http://arxiv.org/abs/2307.10273
Autor:
Mahabadi, Sepideh, Narayanan, Shyam
In this work we consider the diversity maximization problem, where given a data set $X$ of $n$ elements, and a parameter $k$, the goal is to pick a subset of $X$ of size $k$ maximizing a certain diversity measure. [CH01] defined a variety of diversit
Externí odkaz:
http://arxiv.org/abs/2307.04329
Autor:
Aamand, Anders, Andoni, Alexandr, Chen, Justin Y., Indyk, Piotr, Narayanan, Shyam, Silwal, Sandeep
We study statistical/computational tradeoffs for the following density estimation problem: given $k$ distributions $v_1, \ldots, v_k$ over a discrete domain of size $n$, and sampling access to a distribution $p$, identify $v_i$ that is "close" to $p$
Externí odkaz:
http://arxiv.org/abs/2306.11312