42 citations · 111 across the 18 of their papers we have counts for
11 papers · 1 filter
Fundamental limits of over-the-air optimization: Are analog schemes optimal?
Shubham K Jha, Prathamesh Mayekar, Himanshu Tyagi
We consider over-the-air convex optimization on a dimensional space where coded gradients are sent over an additive Gaussian noise channel with variance . The codewords sa…
Phase Transitions for Support Recovery from Gaussian Linear Measurements
Lekshmi Ramesh, Chandra R. Murthy, Himanshu Tyagi
We study the problem of recovering the common -sized support of a set of samples of dimension , using noisy linear measurements per sample. Most prior work has focuse…
Communication Complexity of Distributed High Dimensional Correlation Testing
K. R. Sahasranand, Himanshu Tyagi
Two parties observe independent copies of a -dimensional vector and a scalar. They seek to test if their data is correlated or not, namely they seek to test if the norm $\|ρ\|_2…
Limits on Gradient Compression for Stochastic Optimization
Prathamesh Mayekar, Himanshu Tyagi
We consider stochastic optimization over spaces using access to a first-order oracle. We ask: {What is the minimum precision required for oracle outputs to retain the unre…
Sample-Measurement Tradeoff in Support Recovery under a Subgaussian Prior
Lekshmi Ramesh, Chandra R Murthy, Himanshu Tyagi
Data samples from with a common support of size are accessed through random linear projections (measurements) per sample. It is well-known that roughly …
Communication for Generating Correlation: A Unifying Survey
Madhu Sudan, Himanshu Tyagi, Shun Watanabe
The task of manipulating correlated random variables in a distributed setting has received attention in the fields of both Information Theory and Computer Science. Often shared cor…