10 citations · 10 across the 21 of their papers we have counts for
8 papers · 1 filter
Testing noisy low-degree polynomials for sparsity
Yiqiao Bao, Anindya De, Shivam Nadimpalli +2
We consider the problem of testing whether an unknown low-degree polynomial over is sparse versus far from sparse, given access to noisy evaluations of the polyn…
No Price Tags? No Problem: Query Strategies for Unpriced Information
Shivam Nadimpalli, Mingda Qiao, Ronitt Rubinfeld
The classic *priced query model*, introduced by Charikar et al. (STOC 2000), captures the task of computing a known function on an unknown input when each input variable can only b…
Learning and Testing Convex Functions
Renato Ferreira Pinto, Cassandra Marcussen, Elchanan Mossel +1
We consider the problems of \emph{learning} and \emph{testing} real-valued convex functions over Gaussian space. Despite the extensive study of function convexity across mathematic…
Model-agnostic distribution recovery in high dimension via Fourier measurements
Xi Chen, Anindya De, Yizhi Huang +3
We study the problem of reconstructing an unknown probability distribution to high accuracy, given noisy information about its low-degree Fourier coefficients. Prior results for th…
Halfspaces are hard to test with relative error
Xi Chen, Anindya De, Yizhi Huang +3
Several recent works [DHLNSY25, CPPS25a, CPPS25b] have studied a model of property testing of Boolean functions under a \emph{relative-error} criterion. In this model, the distance…
On the Maximal Gaussian Perimeter of Convex Sets, Revisited
Shivam Nadimpalli, Caleb Pascale
We revisit Nazarov's construction of a convex set with nearly maximal Gaussian surface area and give an alternate analysis based on the notion of convex influence.
Faster exact learning of k-term DNFs with membership and equivalence queries
Josh Alman, Shivam Nadimpalli, Shyamal Patel +1
In 1992 Blum and Rudich [BR92] gave an algorithm that uses membership and equivalence queries to learn -term DNF formulas over in time , improv…
DNF Learning via Locally Mixing Random Walks
Josh Alman, Shivam Nadimpalli, Shyamal Patel +1
We give two results on PAC learning DNF formulas using membership queries in the challenging "distribution-free" learning framework, where learning algorithms must succeed for an a…