Shyamal Patel

collaborators

3 papers

cs.DS2024

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators

Shivam Nadimpalli, Shyamal Patel

We give a non-adaptive algorithm that makes $2^{O ~ (k l o g (1/ ε_{2} - ε_{1}))}$ queries to a Boolean function $f : {\pm 1}^{n} \to {\pm 1}$ and d…

cs.DS2024

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries

Xi Chen, Yumou Fei, Shyamal Patel

We give a distribution-free testing algorithm for decision lists with $O ~ (n^{11/12} / ε^{3})$ queries. This is the first sublinear algorithm for this problem, which sh…

cs.DS2023

New Lower Bounds for Adaptive Tolerant Junta Testing

Xi Chen, Shyamal Patel

We prove a $k^{- Ω (l o g (ε_{2} - ε_{1}))}$ lower bound for adaptively testing whether a Boolean function is $ε_{1}$ -close to or $ε_{2}$ -far from $k$ -j…