Author name cluster

Shyamal Patel

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

2 author rows

STOC Conference 2025 Conference Paper

DNF Learning via Locally Mixing Random Walks

Josh Alman
Shivam Nadimpalli
Shyamal Patel
Rocco A. Servedio

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 arbitrary and unknown distribution over {0,1} n . (1) We first give a quasi-polynomial time “list-decoding” algorithm for learning a single term of an unknown DNF formula. More precisely, for any target s -term DNF formula f = T 1 ∨ ⋯ ∨ T s over {0,1} n and any unknown distribution D over {0,1} n , our algorithm, which uses membership queries and random examples from D , runs in quasipoly( n , s ) time and outputs a list L of candidate terms such that with high probability some term T i of f belongs to L . (2) We then use result (1) to give a quasipoly( n , s )-time algorithm, in the distribution-free PAC learning model with membership queries, for learning the class of size- s DNFs in which all terms have the same size. Our algorithm learns using a DNF hypothesis. The key tool used to establish result (1) is a new result on “locally mixing random walks,” which, roughly speaking, shows that a random walk on a graph that is covered by a small number of expanders has a non-negligible probability of mixing quickly in a subset of these expanders.

Details

FOCS Conference 2025 Conference Paper

Faster Exact Learning of k-Term DNFs with Membership and Equivalence Queries

Josh Alman
Shivam Nadimpalli
Shyamal Patel
Rocco A. Servedio

In 1992 Blum and Rudich [1] gave an algorithm that uses membership and equivalence queries to learn k-term DNF formulas over $\{0, 1\}^{n}$ in time $\operatorname{poly}\left(n, 2^{k}\right)$, improving on the naive $O\left(n^{k}\right)$ running time that can be achieved without membership queries [2]. Since then, many alternative algorithms [3]–[6] have been given which also achieve runtime poly $\left(n, 2^{k}\right)$. We give an algorithm that uses membership and equivalence queries to learn k-term DNF formulas in time poly $(n) \cdot 2^{\tilde{O}(\sqrt{k})}$. This is the first improvement for this problem since the original work of Blum and Rudich [1]. Our approach employs the Winnow2 algorithm for learning linear threshold functions over an enhanced feature space which is adaptively constructed using membership queries. It combines a strengthened version of a technique that effectively reduces the length of DNF terms from the original work of [1] with a range of additional algorithmic tools (attribute-efficient learning algorithms for low-weight linear threshold functions and techniques for finding relevant variables from junta testing) and analytic ingredients (extremal polynomials and noise operators) that are novel in the context of query-based DNF learning.

Details

STOC Conference 2024 Conference Paper

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

Xi Chen 0001
Yumou Fei
Shyamal Patel

We give a distribution-free testing algorithm for decision lists with Õ( n 11/12 /ε 3 ) queries. This is the first sublinear algorithm for this problem, which shows that, unlike halfspaces, testing is strictly easier than learning for decision lists. Complementing the algorithm, we show that any distribution-free tester for decision lists must make Ω(√ n ) queries, or draw Ω( n ) samples when the algorithm is sample-based.

Details

STOC Conference 2024 Conference Paper

Optimal Non-adaptive Tolerant Junta Testing via Local Estimators

Shivam Nadimpalli
Shyamal Patel

We give a non-adaptive algorithm that makes 2 O (√ k log(1/ε 2 − ε 1 )) queries to a Boolean function f :{±1} n →{±1} and distinguishes between f being ε 1 -close to some k -junta versus ε 2 -far from every k -junta. At the heart of our algorithm is a local mean estimation procedure for Boolean functions that may be of independent interest. We complement our upper bound with a matching lower bound, improving a recent lower bound obtained by Chen et al. We thus obtain the first tight bounds for a natural property of Boolean functions in the tolerant testing model.

Details

STOC Conference 2024 Conference Paper

Polylog-Competitive Deterministic Local Routing and Scheduling

Bernhard Haeupler
Shyamal Patel
Antti Roeyskoe
Cliff Stein 0001
Goran Zuzic

This paper addresses point-to-point packet routing in undirected networks, which is the most important communication primitive in most networks. The main result proves the existence of routing tables that deterministically guarantee a polylog-competitive completion-time: In any undirected network, it is possible to give each node simple stateless deterministic local forwarding rules, such that, any adversarially chosen set of packets are delivered as fast as possible, up to polylog factors. All previous routing strategies crucially required randomization for both route selection and packet scheduling. The core technical contribution of this paper is a new local packet scheduling result of independent interest. This scheduling strategy integrates well with recent sparse semi-oblivious path selection strategies. Such strategies deterministically select not one but several candidate paths for each packet and require a global coordinator to know all packets to adaptively select a single good path from those candidates for each packet. Of course, global knowledge of all packets is exactly what local routing tables cannot have. Another challenge is that, even if a single path is selected for each packet, no strategy for scheduling packets along low-congestion paths that is both local and deterministic is known. Our novel scheduling strategy utilizes the fact that every semi-oblivious routing strategy uses only a small (polynomial) subset of candidate routes. It overcomes the issue of global coordination by furthermore being provably robust to adversarial noise. This avoids the issue of having to choose a single path per packet by treating congestion caused by ineffective candidate paths as noise. Beyond more efficient routing tables, our results can be seen as making progress on fundamental questions regarding the importance and power of randomization in network communications and distributed computing. For example, our results imply the first deterministic universally-optimal algorithms in the distributed supported-CONGEST model for many important global distributed tasks, including computing minimum spanning trees, approximate shortest paths, and part-wise aggregates.

Details

FOCS Conference 2023 Conference Paper

New Lower Bounds for Adaptive Tolerant Junta Testing

Xi Chen
Shyamal Patel

We prove a $k^{-\Omega\left(\log \left(\varepsilon_{2}-\varepsilon_{1}\right)\right)}$ lower bound for adap- tively testing whether a Boolean function is $\varepsilon_{1}$-close to or $\varepsilon_{2}-$ far from k-juntas. Our results provide the first superpolynomial separation between tolerant and non-tolerant testing for a natural property of boolean functions under the adaptive setting. Furthermore, our techniques generalize to show that adaptively testing whether a function is $\varepsilon_{1}$-close to a k-junta or $\varepsilon_{2}$-far from $(k+o(k))$-juntas cannot be done with poly $(k, \left(\varepsilon_{2}-\varepsilon_{1}\right)^{-1})$ queries. This is in contrast to an algorithm by Iyer, Tal and Whitmeyer [CCC 2021] which uses poly $(k, \left(\varepsilon_{2}-\varepsilon_{1}\right)^{-1})$ queries to test whether a function is $\varepsilon_{1}$-close to a k-junta or $\varepsilon_{2}$-far from $O(k /\left(\varepsilon_{2}-\varepsilon_{1}\right)^{2})$-juntas

Details

SODA Conference 2022 Conference Paper

Distribution-free Testing for Halfspaces (Almost) Requires PAC Learning

Xi Chen
Shyamal Patel

It is well known that halfspaces over ℝ n and {0, 1} n are PAC-learnable with Θ( n ) samples. Recently Blais et al. [4] showed that even the easier task of distribution-free sample-based testing requires Ω( n /log n ) samples for halfspaces. In this work we study the distribution-free testing of halfspaces with queries, for which we show that the complexity remains to be. Indeed we prove the following stronger tradeoff result: any distribution-free testing algorithm for halfspaces over {0, 1} n that receives k samples must make queries on the input function, when k satisfies n. 99 ≤ k ≤ O ( n/ log 3 n ). For halfspaces over ℝ n we show that any algorithm that makes a finite number of queries must draw Ω( n /log n ) many samples.

Details

JBHI Journal 2022 Journal Article

Voice Biomarkers of Recovery From Acute Respiratory Illness

Brian Tracey
Shyamal Patel
Yao Zhang
Kara Chappie
Dmitri Volfson
Federico Parisi
Catherine Adans-Dester
Francesco Bertacchi

Voice analysis is an emerging technology which has the potential to provide low-cost, at-home monitoring of symptoms associated with a variety of health conditions. While voice has received significant attention for monitoring neurological disease, few studies have focused on voice changes related to flu-like symptoms. Herein, we investigate the relationship between changes in acoustic features of voice and self-reported symptoms during recovery from a flu-like illness in a cohort of 29 subjects. Acoustic features were automatically extracted from “sick” and “well” visit data collected in the laboratory setting, and feature down-selection was used to identify those that change significantly between visits. The selected acoustic features were extracted from at-home data and used to construct a combined distance metric that correlated with self-reported symptoms (0. 63 rank correlation). Changes in self-reported symptoms corresponding to 10% of the ordinal scale used in the study were detected with an area under the curve of 0. 72. The results show that acoustic features derived from voice recordings may provide an objective measure for diagnosing and monitoring symptoms of respiratory illnesses.

Details DOI

ICRA Conference 2007 Conference Paper

Design, Control and Human Testing of an Active Knee Rehabilitation Orthotic Device

Brian Weinberg
Jason Nikitczuk
Shyamal Patel
Benjamin Patritti
Constantinos Mavroidis
Paolo Bonato
P. Canavan

This paper presents a novel, smart and portable active knee rehabilitation orthotic device (AKROD) designed to train stroke patients to correct knee hyperextension during stance and stiff-legged gait (defined as reduced knee flexion during swing). The knee brace provides variable damping controlled in ways that foster motor recovery in stroke patients. A resistive, variable damper, electro-rheological fluid (ERF) based component is used to facilitate knee flexion during stance by providing resistance to knee buckling. Furthermore, the knee brace is used to assist in knee control during swing, i. e. to allow patients to achieve adequate knee flexion for toe clearance and adequate knee extension in preparation to heel strike. The detailed design of AKROD, the first prototype built, closed loop control results and initial human testing are presented here

Details