Recent work on provably efficient algorithms for learning with distribution shift has focused on two models: PQ learning (Goldwasser et al., 2020) and TDS learning (Klivans et al., 2024). Algorithms for TDS learning are allowed to reject a test set entirely if distribution shift is detected. In contrast, PQ learners may only reject points that are deemed out-of-distribution on an individual basis. Our main result is a surprising equivalence between these two models in the distribution-free setting. In particular, we give an efficient black-box reduction from PQ learning to TDS learning for any Boolean concept class. This equivalence implies the first hardness results for distribution-free TDS learning of basic concept classes such as halfspaces. The main technical contribution underlying our equivalence is a method for boosting, via branching programs, the weak distinguishing power of TDS learners that have rejected the target domain. We also show that giving a learner access to {\em membership queries} sidesteps these hardness results and allows for efficient, distribution-free PQ learnability of halfspaces. Our algorithm iteratively recovers large-margin separators obtained by applying successive Forster transforms on the training data.

The main conceptual contribution of this paper is identifying a previously unnoticed connection between two central problems in computational learning theory and property testing: agnostically learning conjunctions and tolerantly testing juntas. Inspired by this connection, the main technical contribution is a pair of improved algorithms for these two problems.

For any є ∈ (0,1), we give a randomized algorithm which given n points in (d, ℓp) for p ∈ [1,2], constructs a directed graph using O(n2 − Ω(є)) edges in nearly-matching time, such that shortest path lengths approximate ℓp-distances up to a (1 + є)-factor. The graph uses non-metric Steiner nodes (known to be necessary) and improves upon the prior construction of Andoni and Zhang using O(n2−Ω(є2)) edges. We show that our construction is nearly-optimal by showing there exists a set of points in d where any (1+є)-approximate directed Steiner spanner must use Ω(n2 − O(є)) edges.

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.

STOC ’25, Prague, Czechia

We give a distribution-free testing algorithm for decision lists with Õ(n11/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.

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:

We give a non-adaptive algorithm that makes 2O(√klog(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.

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

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/ log3 n). For halfspaces over ℝn we show that any algorithm that makes a finite number of queries must draw Ω(n/log n) many samples.

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.

We give a short and easy upper bound on the worst-case size of fault tolerant spanners, which improves on all prior work and is fully optimal at least in the setting of vertex faults.

Motivated by a need for accurate assessment and monitoring of patients with knee osteoarthritis in an ambulatory setting, a wearable electrogoniometer composed of a knee angular sensor and a three-axis accelerometer placed on the thigh is developed. Accurate assessment of knee kinematics requires accurate detection of walking amongst dynamic, heterogeneous, and individualized activities of daily living. This paper investigates four different machine learning techniques for detecting occurrences of walking in uncontrolled environments based on a dataset collected from a total of 4 healthy subjects. Multi-class classifier (random forest) based detection method showed the best performance, which supports 90% precision and 75% recall. The in-depth analysis and interpretation of the results show that accurate decision boundaries are necessary between 1) fast walking and descending stairs, 2) slow walking and ascending stairs, as well as 3) slow walking and transitional activities. This work provides a systematic approach to detect occurrences of walking in uncontrolled living conditions, which can also be extended to other activities.

Periodic assessments of motor function in children with Cerebral Palsy can enable clinicians to make more informed decisions about the type and timing of treatment interventions. Current clinical practice is limited to sporadic assessments performed in a clinical environment and hence, not suitable for capturing small changes that occur longitudinally. We have developed a shoe-based wearable sensor system that allows unobtrusive long-term collection of center of pressure data in the home setting. So far the shoe-based system has been used to collect data from 15 subjects under supervised and semi-supervised settings. In this paper, we present a novel methodology, based on the analysis of center of pressure trajectories using Active Shape Models, for automated clinical assessment of gait deviations in children with Cerebral Palsy. We show that Active Shape Models can be used to effectively model characteristics of the center of pressure trajectories that are associated with specific aspects of gait deviations. A support vector machine classifier, trained on features derived from the Active Shape Models, is able to achieve an accuracy of greater than 90% at classifying clinical scores of gait deviation severity.

We present MercuryLive, a web-enhanced extension to a body sensor network platform for continuous home-based body motion sensing, interactive supervised data collection sessions, and long-term activity data analysis. The major goal of MercuryLive is to enable practical long-term health monitoring in a home setting and henceforth reduce the effort and cost for collecting clinically relevant quantitative measures on patients' health conditions during daily activities. MercuryLive contains three tiers: a central web server for streaming and storage of sensor data, a sensor data collection engine, and a user-friendly web-based GUI client. The platform is currently used in clinical studies on Parkinson's disease.

Quantitative assessment of motor abilities in stroke survivors can provide valuable feedback to guide clinical interventions. Numerous clinical scales were developed in the past to assess levels of impairment and functional limitation in individuals after stroke. The Functional Ability Scale is one of these clinical scales. It is a 75-point scale used to evaluate the functional ability of subjects by grading movement quality during performance of 15 motor tasks. Performance of these motor tasks requires subjects to reach for objects (e.g., a pencil on a table) and manipulate them (e.g., lift the pencil). In this paper, we show that accelerometer data recorded during performance of a subset of the motor tasks pertaining to the Functional Ability Scale can be relied upon to derive accurate estimates of the scores provided by a clinician using this scale. Accelerometer-based estimates of clinical scores were obtained by segmenting the recordings into movement components (reaching, manipulation, release/return), extracting data features, selecting features that maximized the separation among classes associated with different clinical scores, feeding these features to Random Forests to estimate scores for individual motor tasks, and using a linear equation to estimate the total Functional Ability Scale score based on the sum of the clinical scores for individual motor tasks derived from the accelerometer data. Results showed that it is possible to achieve estimates of the total Functional Ability Scale score marked by a bias of only 0.04 points of the scale and a standard deviation of only 2.43 points when using as few as three sensors to collect data during performance of only six motor tasks.

This paper describes Mercury, a wearable, wireless sensor platform for motion analysis of patients being treated for neuromotor disorders, such as Parkinson's Disease, epilepsy, and stroke. In contrast to previous systems intended for short-term use in a laboratory, Mercury is designed to support long-term, longitudinal data collection on patients in hospital and home settings. Patients wear up to 8 wireless nodes equipped with sensors for monitoring movement and physiological conditions. Individual nodes compute high-level features from the raw signals, and a base station performs data collection and tunes sensor node parameters based on energy availability, radio link quality, and application specific policies.

This paper presents the results of a pilot study to assess the feasibility of using accelerometer data to estimate the severity of symptoms and motor complications in patients with Parkinson's disease. A support vector machine (SVM) classifier was implemented to estimate the severity of tremor, bradykinesia and dyskinesia from accelerometer data features. SVM-based estimates were compared with clinical scores derived via visual inspection of video recordings taken while patients performed a series of standardized motor tasks. The analysis of the video recordings was performed by clinicians trained in the use of scales for the assessment of the severity of Parkinsonian symptoms and motor complications. Results derived from the accelerometer time series were analyzed to assess the effect on the estimation of clinical scores of the duration of the window utilized to derive segments (to eventually compute data features) from the accelerometer data, the use of different SVM kernels and misclassification cost values, and the use of data features derived from different motor tasks. Results were also analyzed to assess which combinations of data features carried enough information to reliably assess the severity of symptoms and motor complications. Combinations of data features were compared taking into consideration the computational cost associated with estimating each data feature on the nodes of a body sensor network and the effect of using such data features on the reliability of SVM-based estimates of the severity of Parkinsonian symptoms and motor complications.

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

The goal of this project is to develop wireless sensors and analysis methods to monitor patients with various motor dysfunctions. We are currently targeting two specific applications: facilitating medication titration in patients with Parkinson's disease and assessing motor recovery in stroke survivors undergoing rehabilitation. In our vision, the treatment and rehabilitation hospital of the future will allow clinicians to continuously monitor motor activity in patients via miniature sensor technology in order to better design interventions on an individual basis. Two key points toward developing the tools necessary to achieve continuous monitoring of motor function are (1) development of a robust and deployable wearable wireless network of sensors and (2) the development of analysis techniques to derive clinically relevant information from miniature sensor data.