In sparse Erdős-Rényi graphs, it is known that a linear-time algorithm of Karp and Sipser achieves near-optimal matching sizes asymptotically almost surely, giving a law-of-large numbers for the matching numbers of such graphs in terms of solutions to an ODE [Jonathan Aronson et al., 1998]. We provide an extension of this analysis, identifying broad ranges of stochastic block model parameters for which the Karp-Sipser algorithm achieves near-optimal matching sizes, but demonstrating that it cannot perform optimally on general stochastic block model instances. We also consider the problem of constructing a matching online, in which the vertices of one half of a bipartite stochastic block model arrive one-at-a-time, and must be matched as they arrive. We show that, when the expected degrees in all communities are equal, the competitive ratio lower bound of 0.837 found by Mastin and Jaillet for the Erdős-Rényi case [Andrew Mastin and Patrick Jaillet, 2013] is achieved by a simple greedy algorithm, and this competitive ratio is optimal. We then propose and analyze a linear-time online matching algorithm with better performance in general stochastic block models.

We study processes of societal knowledge accumulation, where the validity of a new unit of knowledge depends both on the correctness of its derivation and on the validity of the units it depends on. A fundamental question in this setting is: If a constant fraction of the new derivations is wrong, can investing a constant fraction, bounded away from one, of effort ensure that a constant fraction of knowledge in society is valid? Ben-Eliezer, Mikulincer, Mossel, and Sudan (ITCS 2023) introduced a concrete probabilistic model to analyze such questions and showed an affirmative answer to this question. Their study, however, focuses on the simple case where each new unit depends on just one existing unit, and units attach according to a {\em preferential attachment rule}. In this work, we consider much more general families of cumulative knowledge processes, where new units may attach according to varied attachment mechanisms and depend on multiple existing units. We also allow a (random) fraction of insertions of adversarial nodes. We give a robust affirmative answer to the above question by showing that for \textit{all} of these models, as long as many of the units follow simple heuristics for checking a bounded number of units they depend on, all errors will be eventually eliminated. Our results indicate that preserving the quality of large interdependent collections of units of knowledge is feasible, as long as careful but not too costly checks are performed when new units are derived/deposited.

Recent work in prosthetic devices suggests that forearm surface electromyography (sEMG) is a promising technology for human-computer interactions. Specifically, a system able to detect individual finger movement can have many clinical and nonclinical applications. Popular consumer-grade sEMG armbands are limited by their fixed electrode arrangement, which can negatively affect the classification of subtle finger gestures. We propose a low-cost, 3D-printed armband with fully adjustable electrode placement for the detection of single-finger tapping motions. We trained machine learning classifiers on features extracted from eight-channel sEMG signals to detect movement from nine fingers. We obtained a classification accuracy of 71.5 ± 1.1% for a K-Nearest Neighbours (KNN) classifier using features extracted from 500 ms windows of sEMG data. Moreover, a KNN model trained on 200 ms windows from a subset of particularly clean data obtained an accuracy of 93.0 ± 0.5%. We also introduce a novel haptic feedback mechanism to improve user experience when using the armband, and propose an augmented reality typing interface as a potential application of our armband.

Wheelchairs controlled using electroencephalography (EEG) have been proposed to facilitate independent mobility for people with motor disabilities. To date, the majority of these systems have relied on distracting external stimuli such as flashing lights and expensive, medical-grade EEG amplifiers. We propose a wheelchair prototype that uses hand motor imagery (MI) and jaw clench data collected with a consumer-grade EEG system to generate left, right, forward, and stop commands. The signal is classified with logistic regression, and using only two scalp electrodes and a two-second window size, we obtained a mean subject accuracy of 60 ± 5% and a peak subject accuracy of 82± 3%. We introduce a novel control-flow paradigm relying on an intermediate control state, engaged by jaw clenching, to reduce the complexity of our classification problem, as well as real-time spectrograms for neurofeedback training. Additionally, we supplement our system with automated driving features, a location tracker, and a heart-rate monitor to increase usability and safety.