1 citations · 1 across the 16 of their papers we have counts for
9 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…
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…
Relative-error unateness testing
Xi Chen, Diptaksho Palit, Kabir Peshawaria +3
The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [CDH+24][CPPS25a][CPPS25b] In this paper we consider th…
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…
A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
Xi Chen, Shyamal Patel, Rocco A. Servedio
The main conceptual contribution of this paper is identifying a previously unnoticed connection between two central problems in computational learning theory and property testing:…
Testing Juntas and Junta Subclasses with Relative Error
Xi Chen, William Pires, Toniann Pitassi +1
This papers considers the junta testing problem in a recently introduced ``relative error'' variant of the standard Boolean function property testing model. In relative-error testi…
Relative-error testing of conjunctions and decision lists
Xi Chen, William Pires, Toniann Pitassi +1
We study the relative-error property testing model for Boolean functions that was recently introduced in the work of Chen et al. (SODA 2025). In relative-error testing, the testing…