Search

This paper describes an efficient algorithm for solving noisy linear inverse problems using pretrained diffusion models. Extending the paradigm of denoising diffusion implicit models (DDIM), we propose constrained diffusion implicit models (CDIM) that modify the diffusion updates to enforce a constraint upon the final output. For noiseless inverse problems, CDIM exactly satisfies the constraints; in the noisy case, we generalize CDIM to satisfy an exact constraint on the residual distribution of the noise. Experiments across a variety of tasks and metrics show strong performance of CDIM, with analogous inference acceleration to unconstrained DDIM: 10 to 50 times faster than previous conditional diffusion methods. We demonstrate the versatility of our approach on many problems including super-resolution, denoising, inpainting, deblurring, and 3D point cloud reconstruction.

We study algorithms for approximating the spectral density of a symmetric matrix $A$ that is accessed through matrix-vector product queries. By combining a previously studied Chebyshev polynomial moment matching method with a deflation step that approximately projects off the largest magnitude eigendirections of $A$ before estimating the spectral density, we give an $\epsilon\cdot\sigma_\ell(A)$ error approximation to the spectral density in the Wasserstein-$1$ metric using $O(\ell\log n+ 1/\epsilon)$ matrix-vector products, where $\sigma_\ell(A)$ is the $\ell^{th}$ largest singular value of $A$. In the common case when $A$ exhibits fast singular value decay, our bound can be much stronger than prior work, which gives an error bound of $\epsilon \cdot ||A||_2$ using $O(1/\epsilon)$ matrix-vector products. We also show that it is nearly tight: any algorithm giving error $\epsilon \cdot \sigma_\ell(A)$ must use $\Omega(\ell+1/\epsilon)$ matrix-vector products. We further show that the popular Stochastic Lanczos Quadrature (SLQ) method matches the above bound, even though SLQ itself is parameter-free and performs no explicit deflation. This bound explains the strong practical performance of SLQ, and motivates a simple variant of SLQ that achieves an even tighter error bound. Our error bound for SLQ leverages an analysis that views it as an implicit polynomial moment matching method, along with recent results on low-rank approximation with single-vector Krylov methods. We use these results to show that the method can perform implicit deflation as part of moment matching., Comment: 77 pages, 1 figure

The U.S. Medicaid program is experiencing critical challenges that include rapidly increasing healthcare costs, uneven care accessibility, and the challenge associated with addressing a varied set of population health needs. This paper investigates the transformative potential of Artificial Intelligence (AI) in reshaping Medicaid by streamlining operations, improving patient results, and lowering costs. We delve into the pivotal role of AI in predictive analytics, care coordination, the detection of fraud, and personalized medicine. By leveraging insights from advanced data models and addressing challenges particular to Medicaid, we put forward AI-driven solutions that prioritize equitable care and improved public health outcomes. This study underscores the urgency of integrating AI into Medicaid to not only improve operational effectiveness but also to create a more accessible and equitable healthcare system for all beneficiaries.

This paper presents a theoretical framework for an AI-driven data quality monitoring system designed to address the challenges of maintaining data quality in high-volume environments. We examine the limitations of traditional methods in managing the scale, velocity, and variety of big data and propose a conceptual approach leveraging advanced machine learning techniques. Our framework outlines a system architecture that incorporates anomaly detection, classification, and predictive analytics for real-time, scalable data quality management. Key components include an intelligent data ingestion layer, adaptive preprocessing mechanisms, context-aware feature extraction, and AI-based quality assessment modules. A continuous learning paradigm is central to our framework, ensuring adaptability to evolving data patterns and quality requirements. We also address implications for scalability, privacy, and integration within existing data ecosystems. While practical results are not provided, it lays a robust theoretical foundation for future research and implementations, advancing data quality management and encouraging the exploration of AI-driven solutions in dynamic environments.

Robotics Process Automation is revolutionizing business operations by significantly enhancing efficiency, productivity, and operational excellence across various industries. This manuscript delivers a comprehensive review of recent advancements in RPA technologies and proposes a novel model designed to elevate RPA capabilities., Comment: 9 pages. European Journal of Computer Science and Information Technology 2024

Deploying large language models (LLMs) locally on mobile devices is advantageous in scenarios where transmitting data to remote cloud servers is either undesirable due to privacy concerns or impractical due to network connection. Recent advancements (MLC, 2023a; Gerganov, 2023) have facilitated the local deployment of LLMs. However, local deployment also presents challenges, particularly in balancing quality (generative performance), latency, and throughput within the hardware constraints of mobile devices. In this paper, we introduce our lightweight, all-in-one automated benchmarking framework that allows users to evaluate LLMs on mobile devices. We provide a comprehensive benchmark of various popular LLMs with different quantization configurations (both weights and activations) across multiple mobile platforms with varying hardware capabilities. Unlike traditional benchmarks that assess full-scale models on high-end GPU clusters, we focus on evaluating resource efficiency (memory and power consumption) and harmful output for compressed models on mobile devices. Our key observations include i) differences in energy efficiency and throughput across mobile platforms; ii) the impact of quantization on memory usage, GPU execution time, and power consumption; and iii) accuracy and performance degradation of quantized models compared to their non-quantized counterparts; and iv) the frequency of hallucinations and toxic content generated by compressed LLMs on mobile devices., Comment: 10 pages

We study the minimum spanning tree (MST) problem in the massively parallel computation (MPC) model. Our focus is particularly on the *strictly sublinear* regime of MPC where the space per machine is $O(n^\delta)$. Here $n$ is the number of vertices and constant $\delta \in (0, 1)$ can be made arbitrarily small. The MST problem admits a simple and folklore $O(\log n)$-round algorithm in the MPC model. When the weights can be arbitrary, this matches a conditional lower bound of $\Omega(\log n)$ which follows from a well-known 1vs2-Cycle conjecture. As such, much of the literature focuses on breaking the logarithmic barrier in more structured variants of the problem, such as when the vertices correspond to points in low- [ANOY14, STOC'14] or high-dimensional Euclidean spaces [JMNZ, SODA'24]. In this work, we focus more generally on metric spaces. Namely, all pairwise weights are provided and guaranteed to satisfy the triangle inequality, but are otherwise unconstrained. We show that for any $\varepsilon > 0$, a $(1+\varepsilon)$-approximate MST can be found in $O(\log \frac{1}{\varepsilon} + \log \log n)$ rounds, which is the first $o(\log n)$-round algorithm for finding any constant approximation in this setting. Other than being applicable to more general weight functions, our algorithm also slightly improves the $O(\log \log n \cdot \log \log \log n)$ round-complexity of [JMNZ24, SODA'24] and significantly improves its approximation from a large constant to $1+\varepsilon$. On the lower bound side, we prove that under the 1vs2-Cycle conjecture, $\Omega(\log \frac{1}{\varepsilon})$ rounds are needed for finding a $(1+\varepsilon)$-approximate MST in general metrics. It is worth noting that while many existing lower bounds in the MPC model under the 1vs2-Cycle conjecture only hold against "component stable" algorithms, our lower bound applies to *all* algorithms.

We present foundation language models developed to power Apple Intelligence features, including a ~3 billion parameter model designed to run efficiently on devices and a large server-based language model designed for Private Cloud Compute. These models are designed to perform a wide range of tasks efficiently, accurately, and responsibly. This report describes the model architecture, the data used to train the model, the training process, how the models are optimized for inference, and the evaluation results. We highlight our focus on Responsible AI and how the principles are applied throughout the model development.

In time-domain radio astronomy with arrays, voltages from individual antennas are added together with proper delay and fringe correction to form the beam in real-time. In order to achieve the correct phased addition of antenna voltages one has to also correct for the ionospheric and instrumental gains. Conventionally this is done using observations of a calibrator source located near to the target field. This scheme is sub-optimal since it does not correct for the variation of the gains with time and position in the sky. Further, since the ionospheric phase variation is typically most rapid at the longest baselines, the most distant antennas are often excluded while forming the beam. We present here a different methodology ("in-field phasing"), in which the gains are obtained in real-time using a model of the intensity distribution in the target field, which overcomes all of these drawbacks. We present observations with the upgraded Giant Metrewave Radio Telescope (uGMRT) which demonstrates that in-field phasing does lead to a significant improvement in sensitivity. We also show, using observations of the millisecond pulsar J1120$-$3618 that this in turn leads to a significant improvement of measurements of the Dispersion Measure and Time of Arrival. Finally, we present test observations of the GMRT discovered eclipsing black widow pulsar J1544+4937 showing that in-field phasing leads to improvement in the measurement of the cut-off frequency of the eclipse., Comment: Accepted for publication in the ApJ

Backdoor data poisoning, inserted within instruction examples used to fine-tune a foundation Large Language Model (LLM) for downstream tasks (\textit{e.g.,} sentiment prediction), is a serious security concern due to the evasive nature of such attacks. The poisoning is usually in the form of a (seemingly innocuous) trigger word or phrase inserted into a very small fraction of the fine-tuning samples from a target class. Such backdoor attacks can: alter response sentiment, violate censorship, over-refuse (invoke censorship for legitimate queries), inject false content, or trigger nonsense responses (hallucinations). In this work we investigate the efficacy of instruction fine-tuning backdoor attacks as attack "hyperparameters" are varied under a variety of scenarios, considering: the trigger location in the poisoned examples; robustness to change in the trigger location, partial triggers, and synonym substitutions at test time; attack transfer from one (fine-tuning) domain to a related test domain; and clean-label vs. dirty-label poisoning. Based on our observations, we propose and evaluate two defenses against these attacks: i) a \textit{during-fine-tuning defense} based on word-frequency counts that assumes the (possibly poisoned) fine-tuning dataset is available and identifies the backdoor trigger tokens; and ii) a \textit{post-fine-tuning defense} based on downstream clean fine-tuning of the backdoored LLM with a small defense dataset. Finally, we provide a brief survey of related work on backdoor attacks and defenses., Comment: Under review

In this paper, we study streaming algorithms that minimize the number of changes made to their internal state (i.e., memory contents). While the design of streaming algorithms typically focuses on minimizing space and update time, these metrics fail to capture the asymmetric costs, inherent in modern hardware and database systems, of reading versus writing to memory. In fact, most streaming algorithms write to their memory on every update, which is undesirable when writing is significantly more expensive than reading. This raises the question of whether streaming algorithms with small space and number of memory writes are possible. We first demonstrate that, for the fundamental $F_p$ moment estimation problem with $p\ge 1$, any streaming algorithm that achieves a constant factor approximation must make $\Omega(n^{1-1/p})$ internal state changes, regardless of how much space it uses. Perhaps surprisingly, we show that this lower bound can be matched by an algorithm that also has near-optimal space complexity. Specifically, we give a $(1+\varepsilon)$-approximation algorithm for $F_p$ moment estimation that uses a near-optimal $\widetilde{\mathcal{O}}_\varepsilon(n^{1-1/p})$ number of state changes, while simultaneously achieving near-optimal space, i.e., for $p\in[1,2]$, our algorithm uses $\text{poly}\left(\log n,\frac{1}{\varepsilon}\right)$ bits of space, while for $p>2$, the algorithm uses $\widetilde{\mathcal{O}}_\varepsilon(n^{1-2/p})$ space. We similarly design streaming algorithms that are simultaneously near-optimal in both space complexity and the number of state changes for the heavy-hitters problem, sparse support recovery, and entropy estimation. Our results demonstrate that an optimal number of state changes can be achieved without sacrificing space complexity., Comment: PODS 2024

We give an efficient algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a $c$-approximate clustering in roughly $n^{1+O(1/c^2)}$ time. We obtain our result by combining a new Centroid-Linkage HAC algorithm with a novel fully dynamic data structure for nearest neighbor search which works under adaptive updates. We also evaluate our algorithm empirically. By leveraging a state-of-the-art nearest-neighbor search library, we obtain a fast and accurate Centroid-Linkage HAC algorithm. Compared to an existing state-of-the-art exact baseline, our implementation maintains the clustering quality while delivering up to a $36\times$ speedup due to performing fewer distance comparisons.

In this paper, we present XctDiff, an algorithm framework for reconstructing CT from a single radiograph, which decomposes the reconstruction process into two easily controllable tasks: feature extraction and CT reconstruction. Specifically, we first design a progressive feature extraction strategy that is able to extract robust 3D priors from radiographs. Then, we use the extracted prior information to guide the CT reconstruction in the latent space. Moreover, we design a homogeneous spatial codebook to improve the reconstruction quality further. The experimental results show that our proposed method achieves state-of-the-art reconstruction performance and overcomes the blurring issue. We also apply XctDiff on self-supervised pre-training task. The effectiveness indicates that it has promising additional applications in medical image analysis. The code is available at:https://github.com/qingze-bai/XctDiff

Neural embedding models have become a fundamental component of modern information retrieval (IR) pipelines. These models produce a single embedding $x \in \mathbb{R}^d$ per data-point, allowing for fast retrieval via highly optimized maximum inner product search (MIPS) algorithms. Recently, beginning with the landmark ColBERT paper, multi-vector models, which produce a set of embedding per data point, have achieved markedly superior performance for IR tasks. Unfortunately, using these models for IR is computationally expensive due to the increased complexity of multi-vector retrieval and scoring. In this paper, we introduce MUVERA (MUlti-VEctor Retrieval Algorithm), a retrieval mechanism which reduces multi-vector similarity search to single-vector similarity search. This enables the usage of off-the-shelf MIPS solvers for multi-vector retrieval. MUVERA asymmetrically generates Fixed Dimensional Encodings (FDEs) of queries and documents, which are vectors whose inner product approximates multi-vector similarity. We prove that FDEs give high-quality $\epsilon$-approximations, thus providing the first single-vector proxy for multi-vector similarity with theoretical guarantees. Empirically, we find that FDEs achieve the same recall as prior state-of-the-art heuristics while retrieving 2-5$\times$ fewer candidates. Compared to prior state of the art implementations, MUVERA achieves consistently good end-to-end recall and latency across a diverse set of the BEIR retrieval datasets, achieving an average of 10$\%$ improved recall with $90\%$ lower latency.

We consider the PageRank problem in the dynamic setting, where the goal is to explicitly maintain an approximate PageRank vector $\pi \in \mathbb{R}^n$ for a graph under a sequence of edge insertions and deletions. Our main result is a complete characterization of the complexity of dynamic PageRank maintenance for both multiplicative and additive ($L_1$) approximations. First, we establish matching lower and upper bounds for maintaining additive approximate PageRank in both incremental and decremental settings. In particular, we demonstrate that in the worst-case $(1/\alpha)^{\Theta(\log \log n)}$ update time is necessary and sufficient for this problem, where $\alpha$ is the desired additive approximation. On the other hand, we demonstrate that the commonly employed ForwardPush approach performs substantially worse than this optimal runtime. Specifically, we show that ForwardPush requires $\Omega(n^{1-\delta})$ time per update on average, for any $\delta > 0$, even in the incremental setting. For multiplicative approximations, however, we demonstrate that the situation is significantly more challenging. Specifically, we prove that any algorithm that explicitly maintains a constant factor multiplicative approximation of the PageRank vector of a directed graph must have amortized update time $\Omega(n^{1-\delta})$, for any $\delta > 0$, even in the incremental setting, thereby resolving a 13-year old open question of Bahmani et al.~(VLDB 2010). This sharply contrasts with the undirected setting, where we show that $\rm{poly}\ \log n$ update time is feasible, even in the fully dynamic setting under oblivious adversary.

Average linkage Hierarchical Agglomerative Clustering (HAC) is an extensively studied and applied method for hierarchical clustering. Recent applications to massive datasets have driven significant interest in near-linear-time and efficient parallel algorithms for average linkage HAC. We provide hardness results that rule out such algorithms. On the sequential side, we establish a runtime lower bound of $n^{3/2-\epsilon}$ on $n$ node graphs for sequential combinatorial algorithms under standard fine-grained complexity assumptions. This essentially matches the best-known running time for average linkage HAC. On the parallel side, we prove that average linkage HAC likely cannot be parallelized even on simple graphs by showing that it is CC-hard on trees of diameter $4$. On the possibility side, we demonstrate that average linkage HAC can be efficiently parallelized (i.e., it is in NC) on paths and can be solved in near-linear time when the height of the output cluster hierarchy is small., Comment: To appear at ICALP 2024

We present the first estimate, based on direct HI 21 cm observations, of the HI mass function (HIMF) of star-forming galaxies at $z\approx1$, obtained by combining our measurement of the scaling relation between HI mass ($M_{HI}$) and B-band luminosity ($M_B$) of star-forming galaxies with literature estimates of the B-band luminosity function at $z\approx1$. We determined the $M_{HI}-M_B$ relation by using the GMRT-CATz1 survey of the DEEP2 fields to measure the average HI mass of blue galaxies at $z=0.74-1.45$ in three separate $M_B$ subsamples. This was done by separately stacking the HI 21 cm emission signals of the galaxies in each subsample to detect, at (3.5-4.4)$\sigma$ significance, the average HI 21 cm emission of each subsample. We find that the $M_{HI}-M_B$ relation at $z\approx1$ is consistent with that at $z\approx0$. We combine our estimate of the $M_{HI}-M_B$ relation at $z\approx1$ with the B-band luminosity function at $z\approx1$ to determine the HIMF at $z\approx1$. We find that the number density of galaxies with $M_{HI}>10^{10} M_\odot$ (higher than the knee of the local HIMF) at $z\approx1$ is a factor of $\approx4-5$ higher than that at $z\approx0$, for a wide range of assumed scatters in the $M_{HI}-M_B$ relation. We rule out the hypothesis that the number density of galaxies with $M_{HI}>10^{10} M_\odot$ remains unchanged between $z \approx 1$ and $z\approx0$ at $\gtrsim99.7$\% confidence. This is the first statistically significant evidence for evolution in the HIMF of galaxies from the epoch of cosmic noon., Comment: 9 pages, 5 figures; minor changes to match version in press at ApJ Letters

The rapid development of computer network system brings both a great convenience and new security threats for users. Network security problem generally includes network system security and data security. Specifically, it refers to the reliability of network system, confidentiality, integrity and availability of data information in the system. This paper introduces the significance of network security systems and highlights related technologies, mainly authentication, data encryption, firewall and antivirus technology. Network security problems can be faced by any network user, therefore we must greatly prioritize network security, try to prevent hostile attacks and ensure the overall security of the network system.

In this report, we introduce the Gemini 1.5 family of models, representing the next generation of highly compute-efficient multimodal models capable of recalling and reasoning over fine-grained information from millions of tokens of context, including multiple long documents and hours of video and audio. The family includes two new models: (1) an updated Gemini 1.5 Pro, which exceeds the February version on the great majority of capabilities and benchmarks; (2) Gemini 1.5 Flash, a more lightweight variant designed for efficiency with minimal regression in quality. Gemini 1.5 models achieve near-perfect recall on long-context retrieval tasks across modalities, improve the state-of-the-art in long-document QA, long-video QA and long-context ASR, and match or surpass Gemini 1.0 Ultra's state-of-the-art performance across a broad set of benchmarks. Studying the limits of Gemini 1.5's long-context ability, we find continued improvement in next-token prediction and near-perfect retrieval (>99%) up to at least 10M tokens, a generational leap over existing models such as Claude 3.0 (200k) and GPT-4 Turbo (128k). Finally, we highlight real-world use cases, such as Gemini 1.5 collaborating with professionals on completing their tasks achieving 26 to 75% time savings across 10 different job categories, as well as surprising new capabilities of large language models at the frontier; when given a grammar manual for Kalamang, a language with fewer than 200 speakers worldwide, the model learns to translate English to Kalamang at a similar level to a person who learned from the same content.

We give new data-dependent locality sensitive hashing schemes (LSH) for the Earth Mover's Distance ($\mathsf{EMD}$), and as a result, improve the best approximation for nearest neighbor search under $\mathsf{EMD}$ by a quadratic factor. Here, the metric $\mathsf{EMD}_s(\mathbb{R}^d,\ell_p)$ consists of sets of $s$ vectors in $\mathbb{R}^d$, and for any two sets $x,y$ of $s$ vectors the distance $\mathsf{EMD}(x,y)$ is the minimum cost of a perfect matching between $x,y$, where the cost of matching two vectors is their $\ell_p$ distance. Previously, Andoni, Indyk, and Krauthgamer gave a (data-independent) locality-sensitive hashing scheme for $\mathsf{EMD}_s(\mathbb{R}^d,\ell_p)$ when $p \in [1,2]$ with approximation $O(\log^2 s)$. By being data-dependent, we improve the approximation to $\tilde{O}(\log s)$. Our main technical contribution is to show that for any distribution $\mu$ supported on the metric $\mathsf{EMD}_s(\mathbb{R}^d, \ell_p)$, there exists a data-dependent LSH for dense regions of $\mu$ which achieves approximation $\tilde{O}(\log s)$, and that the data-independent LSH actually achieves a $\tilde{O}(\log s)$-approximation outside of those dense regions. Finally, we show how to "glue" together these two hashing schemes without any additional loss in the approximation. Beyond nearest neighbor search, our data-dependent LSH also gives optimal (distributional) sketches for the Earth Mover's Distance. By known sketching lower bounds, this implies that our LSH is optimal (up to $\mathrm{poly}(\log \log s)$ factors) among those that collide close points with constant probability.

We consider the fundamental problem of decomposing a large-scale approximate nearest neighbor search (ANNS) problem into smaller sub-problems. The goal is to partition the input points into neighborhood-preserving shards, so that the nearest neighbors of any point are contained in only a few shards. When a query arrives, a routing algorithm is used to identify the shards which should be searched for its nearest neighbors. This approach forms the backbone of distributed ANNS, where the dataset is so large that it must be split across multiple machines. In this paper, we design simple and highly efficient routing methods, and prove strong theoretical guarantees on their performance. A crucial characteristic of our routing algorithms is that they are inherently modular, and can be used with any partitioning method. This addresses a key drawback of prior approaches, where the routing algorithms are inextricably linked to their associated partitioning method. In particular, our new routing methods enable the use of balanced graph partitioning, which is a high-quality partitioning method without a naturally associated routing algorithm. Thus, we provide the first methods for routing using balanced graph partitioning that are extremely fast to train, admit low latency, and achieve high recall. We provide a comprehensive evaluation of our full partitioning and routing pipeline on billion-scale datasets, where it outperforms existing scalable partitioning methods by significant margins, achieving up to 2.14x higher QPS at 90% recall$@10$ than the best competitor.

Multi-dimensional Scaling (MDS) is a family of methods for embedding an $n$-point metric into low-dimensional Euclidean space. We study the Kamada-Kawai formulation of MDS: given a set of non-negative dissimilarities $\{d_{i,j}\}_{i , j \in [n]}$ over $n$ points, the goal is to find an embedding $\{x_1,\dots,x_n\} \in \mathbb{R}^k$ that minimizes \[\text{OPT} = \min_{x} \mathbb{E}_{i,j \in [n]} \left[ \left(1-\frac{\|x_i - x_j\|}{d_{i,j}}\right)^2 \right] \] Kamada-Kawai provides a more relaxed measure of the quality of a low-dimensional metric embedding than the traditional bi-Lipschitz-ness measure studied in theoretical computer science; this is advantageous because strong hardness-of-approximation results are known for the latter, Kamada-Kawai admits nontrivial approximation algorithms. Despite its popularity, our theoretical understanding of MDS is limited. Recently, Demaine, Hesterberg, Koehler, Lynch, and Urschel (arXiv:2109.11505) gave the first approximation algorithm with provable guarantees for Kamada-Kawai in the constant-$k$ regime, with cost $\text{OPT} +\epsilon$ in $n^2 2^{\text{poly}(\Delta/\epsilon)}$ time, where $\Delta$ is the aspect ratio of the input. In this work, we give the first approximation algorithm for MDS with quasi-polynomial dependency on $\Delta$: we achieve a solution with cost $\tilde{O}(\log \Delta)\text{OPT}^{\Omega(1)}+\epsilon$ in time $n^{O(1)}2^{\text{poly}(\log(\Delta)/\epsilon)}$. Our approach is based on a novel analysis of a conditioning-based rounding scheme for the Sherali-Adams LP Hierarchy. Crucially, our analysis exploits the geometry of low-dimensional Euclidean space, allowing us to avoid an exponential dependence on the aspect ratio. We believe our geometry-aware treatment of the Sherali-Adams Hierarchy is an important step towards developing general-purpose techniques for efficient metric optimization algorithms., Comment: Extended exposition

Head Related Transfer Functions (HRTFs) play a crucial role in creating immersive spatial audio experiences. However, HRTFs differ significantly from person to person, and traditional methods for estimating personalized HRTFs are expensive, time-consuming, and require specialized equipment. We imagine a world where your personalized HRTF can be determined by capturing data through earbuds in everyday environments. In this paper, we propose a novel approach for deriving personalized HRTFs that only relies on in-the-wild binaural recordings and head tracking data. By analyzing how sounds change as the user rotates their head through different environments with different noise sources, we can accurately estimate their personalized HRTF. Our results show that our predicted HRTFs closely match ground-truth HRTFs measured in an anechoic chamber. Furthermore, listening studies demonstrate that our personalized HRTFs significantly improve sound localization and reduce front-back confusion in virtual environments. Our approach offers an efficient and accessible method for deriving personalized HRTFs and has the potential to greatly improve spatial audio experiences., Comment: 9 Pages. Presented at UIST '23

We present here estimates of the average rates of accretion of neutral gas onto main-sequence galaxies and the conversion of atomic gas to molecular gas in these galaxies at two key epochs in galaxy evolution: (i) $z\approx1.3-1.0$, towards the end of the epoch of peak star-formation activity in the Universe, and (ii) $z\approx1-0$, when the star-formation activity declines by an order of magnitude. We determine the net gas accretion rate $\rm{R_{Acc}}$ and the molecular gas formation rate $\rm{R_{Mol}}$ by combining the relations between the stellar mass and the atomic gas mass, the molecular gas mass, and the star-formation rate (SFR) at three epochs, $z=1.3$, $z=1.0$, and $z=0$, with the assumption that galaxies evolve continuously on the star-forming main-sequence. We find that, for all galaxies, $\rm{R_{Acc}}$ is far lower than the average SFR $\rm{R_{SFR}}$ at $z\approx1.3-1.0$; however, $\rm{R_{Mol}}$ is similar to $\rm{R_{SFR}}$ during this interval. Conversely, both $\rm{R_{Mol}}$ and $\rm{R_{Acc}}$ are significantly lower than $\rm{R_{SFR}}$ over the later interval, $z\approx1-0$. We find that massive main-sequence galaxies had already acquired most of their present-day baryonic mass by $z\approx1.3$. At $z\approx1.3-1.0$, the rapid conversion of the existing atomic gas to molecular gas was sufficient to maintain a high average SFR, despite the low net gas accretion rate. However, at later times, the combination of the lower net gas accretion rate and the lower molecular gas formation rate leads to a decline in the fuel available for star-formation, and results in the observed decrease in the SFR density of the Universe over the last 8 Gyr., Comment: 8 pages, 3 figures; Accepted for publication in ApJ Letters

We investigate the structural and dynamic properties of active Brownian particles (APs) confined within a soft annulus-shaped channel. Depending on the strength of the confinement and the P\'eclet number, we observe a novel re-entrant behavior that is not present in unconfined systems. Our findings are substantiated by numerical simulations and analytical considerations, revealing that this behavior arises from the strong coupling between the P\'eclet number and the effective confining dimensionality of the APs. Beyond highlighting the important influence of soft boundaries on APs, our research holds significance for future applications of micro-robotic systems.

We study optimization problems in a metric space $(\mathcal{X},d)$ where we can compute distances in two ways: via a ''strong'' oracle that returns exact distances $d(x,y)$, and a ''weak'' oracle that returns distances $\tilde{d}(x,y)$ which may be arbitrarily corrupted with some probability. This model captures the increasingly common trade-off between employing both an expensive similarity model (e.g. a large-scale embedding model), and a less accurate but cheaper model. Hence, the goal is to make as few queries to the strong oracle as possible. We consider both so-called ''point queries'', where the strong oracle is queried on a set of points $S \subset \mathcal{X} $ and returns $d(x,y)$ for all $x,y \in S$, and ''edge queries'' where it is queried for individual distances $d(x,y)$. Our main contributions are optimal algorithms and lower bounds for clustering and Minimum Spanning Tree (MST) in this model. For $k$-centers, $k$-median, and $k$-means, we give constant factor approximation algorithms with only $\tilde{O}(k)$ strong oracle point queries, and prove that $\Omega(k)$ queries are required for any bounded approximation. For edge queries, our upper and lower bounds are both $\tilde{\Theta}(k^2)$. Surprisingly, for the MST problem we give a $O(\sqrt{\log n})$ approximation algorithm using no strong oracle queries at all, and a matching $\Omega(\sqrt{\log n})$ lower bound. We empirically evaluate our algorithms, and show that their quality is comparable to that of the baseline algorithms that are given all true distances, but while querying the strong oracle on only a small fraction ($<1\%$) of points.

Nitinol is a smart material that can be used as an actuator, a sensor, or a structural element, and has the potential to significantly enhance the capabilities of microrobots. Femtosecond laser technology can be used to process nitinol while avoiding heat-affected zones (HAZ), thus retaining superelastic properties. In this work, we manufacture living hinges of arbitrary cross-sections from nitinol using a femtosecond laser micromachining process. We first determined the laser cutting parameters, 4.1 Jcm^-2 fluence with 5 passes for 5 um ablation, by varying laser power level and number of passes. Next, we modeled the hinges using an analytical model as well as creating an Abaqus finite element method, and showed the accuracy of the models by comparing them to the torque produced by eight different hinges, four with a rectangular cross-section and four with an arc cross-section. Finally, we manufactured three prototype miniature devices to illustrate the usefulness of these nitinol hinges: a sample spherical 5-bar mechanism, a sarrus linkage, and a piezoelectric actuated robotic wing mechanism., Comment: 7 pages, 4 figures, submitted to IEEE RA-L

We present an approximate attention mechanism named HyperAttention to address the computational challenges posed by the growing complexity of long contexts used in Large Language Models (LLMs). Recent work suggests that in the worst-case scenario, quadratic time is necessary unless the entries of the attention matrix are bounded or the matrix has low stable rank. We introduce two parameters which measure: (1) the max column norm in the normalized attention matrix, and (2) the ratio of row norms in the unnormalized attention matrix after detecting and removing large entries. We use these fine-grained parameters to capture the hardness of the problem. Despite previous lower bounds, we are able to achieve a linear time sampling algorithm even when the matrix has unbounded entries or a large stable rank, provided the above parameters are small. HyperAttention features a modular design that easily accommodates integration of other fast low-level implementations, particularly FlashAttention. Empirically, employing Locality Sensitive Hashing (LSH) to identify large entries, HyperAttention outperforms existing methods, giving significant speed improvements compared to state-of-the-art solutions like FlashAttention. We validate the empirical performance of HyperAttention on a variety of different long-context length datasets. For example, HyperAttention makes the inference time of ChatGLM2 50\% faster on 32k context length while perplexity increases from 5.6 to 6.3. On larger context length, e.g., 131k, with causal masking, HyperAttention offers 5-fold speedup on a single attention layer.

Soft compliant microrobots have the potential to deliver significant societal impact when deployed in applications such as search and rescue. In this research we present mCLARI, a body compliant quadrupedal microrobot of 20mm neutral body length and 0.97g, improving on its larger predecessor, CLARI. This robot has four independently actuated leg modules with 2 degrees of freedom, each driven by piezoelectric actuators. The legs are interconnected in a closed kinematic chain via passive body joints, enabling passive body compliance for shape adaptation to external constraints. Despite scaling its larger predecessor down to 60 percent in length and 38 percent in mass, mCLARI maintains 80 percent of the actuation power to achieve high agility. Additionally, we demonstrate the new capability of passively shape-morphing mCLARI - omnidirectional laterally confined locomotion - and experimentally quantify its running performance achieving a new unconstrained top speed of 3 bodylengths/s (60 mms-1). Leveraging passive body compliance, mCLARI can navigate through narrow spaces with a body compression ratio of up to 1.5x the neutral body shape.

Classical motion planning for robotic manipulation includes a set of general algorithms that aim to minimize a scene-specific cost of executing a given plan. This approach offers remarkable adaptability, as they can be directly used off-the-shelf for any new scene without needing specific training datasets. However, without a prior understanding of what diverse valid trajectories are and without specially designed cost functions for a given scene, the overall solutions tend to have low success rates. While deep-learning-based algorithms tremendously improve success rates, they are much harder to adopt without specialized training datasets. We propose EDMP, an Ensemble-of-costs-guided Diffusion for Motion Planning that aims to combine the strengths of classical and deep-learning-based motion planning. Our diffusion-based network is trained on a set of diverse kinematically valid trajectories. Like classical planning, for any new scene at the time of inference, we compute scene-specific costs such as "collision cost" and guide the diffusion to generate valid trajectories that satisfy the scene-specific constraints. Further, instead of a single cost function that may be insufficient in capturing diversity across scenes, we use an ensemble of costs to guide the diffusion process, significantly improving the success rate compared to classical planners. EDMP performs comparably with SOTA deep-learning-based methods while retaining the generalization capabilities primarily associated with classical planners., Comment: 8 pages, 8 figures, submitted to ICRA 2024 (International Conference on Robotics and Automation)

Star-forming galaxies are believed to replenish their atomic gas reservoir, which is consumed in star-formation, through accretion of gas from their circumgalactic mediums (CGMs). However, there are few observational constraints today on the gas accretion rate in external galaxies. Here, we use our recent measurement of the scaling relation between the atomic hydrogen (HI) mass $M_{HI}$ and the stellar mass $M_*$ in star-forming galaxies at $z \approx 0.35$, with the relations between the star-formation rate (SFR) and $M_*$, and the molecular gas mass $M_{Mol}$ and $M_*$, and the assumption that star-forming galaxies evolve along the main sequence, to determine the evolution of the neutral gas reservoir and the average net gas accretion rate onto the disks of star-forming galaxies over the past 4 Gyr. For galaxies with $M_* \gtrsim 10^9 M_{\odot}$ today, we find that both $M_*$ and $M_{HI}$ in the disk have increased, while $M_{Mol}$ has decreased, since $z \sim 0.35$. The average gas accretion rate onto the disk over the past 4 Gyr is similar to the average SFR over this period, implying that main-sequence galaxies have maintained a stable HI reservoir, despite the consumption of gas in star-formation. We obtain an average net gas accretion rate (over the past 4 Gyr) of $\approx 6 M_{\odot} yr^{-1}$ for galaxies with the stellar mass of the Milky Way. At low redshifts, $z \lesssim 0.4$, the reason for the decline in the cosmic SFR density thus appears to be the inefficiency in the conversion of atomic gas to molecular gas, rather than insufficient gas accretion from the CGM., Comment: Accepted for publication in The Astrophysical Journal Letters

Miniature-legged robots are constrained by their onboard computation and control, thus motivating the need for simple, first-principles-based geometric models that connect \emph{periodic actuation or gaits} (a universal robot control paradigm) to the induced average locomotion. In this paper, we develop a \emph{modulable two-beat gait design framework} for sprawled planar quadrupedal systems under the no-slip using tools from geometric mechanics. We reduce standard two-beat gaits into unique subgaits in mutually exclusive shape subspaces. Subgaits are characterized by a locomotive stance phase when limbs are in ground contact and a non-locomotive, instantaneous swing phase where the limbs are reset without contact. During the stance phase, the contacting limbs form a four-bar mechanism. To analyze the ensuing locomotion, we develop the following tools: (a) a vector field to generate nonslip actuation, (b) the kinematics of a four-bar mechanism as a local connection, and (c) stratified panels that combine the kinematics and constrained actuation to encode the net change in the system's position generated by a stance-swing subgait cycle. Decoupled subgaits are then designed independently using flows on the shape-change basis and are combined with appropriate phasing to produce a two-beat gait. Further, we introduce ``scaling" and ``sliding" control inputs to continuously modulate the global trajectories of the quadrupedal system in gait time through which we demonstrate cycle-average speed, direction, and steering control using the control inputs. Thus, this framework has the potential to create uncomplicated open-loop gait plans or gain schedules for robots with limited resources, bringing them closer to achieving autonomous control., Comment: 8 pages, 6 figures

This paper presents the design and implementation of FLIPS, a middleware system to manage data and participant heterogeneity in federated learning (FL) training workloads. In particular, we examine the benefits of label distribution clustering on participant selection in federated learning. FLIPS clusters parties involved in an FL training job based on the label distribution of their data apriori, and during FL training, ensures that each cluster is equitably represented in the participants selected. FLIPS can support the most common FL algorithms, including FedAvg, FedProx, FedDyn, FedOpt and FedYogi. To manage platform heterogeneity and dynamic resource availability, FLIPS incorporates a straggler management mechanism to handle changing capacities in distributed, smart community applications. Privacy of label distributions, clustering and participant selection is ensured through a trusted execution environment (TEE). Our comprehensive empirical evaluation compares FLIPS with random participant selection, as well as three other "smart" selection mechanisms - Oort, TiFL and gradient clustering using two real-world datasets, two benchmark datasets, two different non-IID distributions and three common FL algorithms (FedYogi, FedProx and FedAvg). We demonstrate that FLIPS significantly improves convergence, achieving higher accuracy by 17 - 20 % with 20 - 60 % lower communication costs, and these benefits endure in the presence of straggler participants.

We study the classic Euclidean Minimum Spanning Tree (MST) problem in the Massively Parallel Computation (MPC) model. Given a set $X \subset \mathbb{R}^d$ of $n$ points, the goal is to produce a spanning tree for $X$ with weight within a small factor of optimal. Euclidean MST is one of the most fundamental hierarchical geometric clustering algorithms, and with the proliferation of enormous high-dimensional data sets, such as massive transformer-based embeddings, there is now a critical demand for efficient distributed algorithms to cluster such data sets. In low-dimensional space, where $d = O(1)$, Andoni, Nikolov, Onak, and Yaroslavtsev [STOC '14] gave a constant round MPC algorithm that obtains a high accuracy $(1+\epsilon)$-approximate solution. However, the situation is much more challenging for high-dimensional spaces: the best-known algorithm to obtain a constant approximation requires $O(\log n)$ rounds. Recently Chen, Jayaram, Levi, and Waingarten [STOC '22] gave a $\tilde{O}(\log n)$ approximation algorithm in a constant number of rounds based on embeddings into tree metrics. However, to date, no known algorithm achieves both a constant number of rounds and approximation. In this paper, we make strong progress on this front by giving a constant factor approximation in $\tilde{O}(\log \log n)$ rounds of the MPC model. In contrast to tree-embedding-based approaches, which necessarily must pay $\Omega(\log n)$-distortion, our algorithm is based on a new combination of graph-based distributed MST algorithms and geometric space partitions. Additionally, although the approximate MST we return can have a large depth, we show that it can be modified to obtain a $\tilde{O}(\log \log n)$-round constant factor approximation to the Euclidean Traveling Salesman Problem (TSP) in the MPC model. Previously, only a $O(\log n)$ round was known for the problem.

We study the consistent k-center clustering problem. In this problem, the goal is to maintain a constant factor approximate $k$-center solution during a sequence of $n$ point insertions and deletions while minimizing the recourse, i.e., the number of changes made to the set of centers after each point insertion or deletion. Previous works by Lattanzi and Vassilvitskii [ICML '12] and Fichtenberger, Lattanzi, Norouzi-Fard, and Svensson [SODA '21] showed that in the incremental setting, where deletions are not allowed, one can obtain $k \cdot \textrm{polylog}(n) / n$ amortized recourse for both $k$-center and $k$-median, and demonstrated a matching lower bound. However, no algorithm for the fully dynamic setting achieves less than the trivial $O(k)$ changes per update, which can be obtained by simply reclustering the full dataset after every update. In this work, we give the first algorithm for consistent $k$-center clustering for the fully dynamic setting, i.e., when both point insertions and deletions are allowed, and improves upon a trivial $O(k)$ recourse bound. Specifically, our algorithm maintains a constant factor approximate solution while ensuring worst-case constant recourse per update, which is optimal in the fully dynamic setting. Moreover, our algorithm is deterministic and is therefore correct even if an adaptive adversary chooses the insertions and deletions.

Active fluids composed of constituents that are constantly driven away from thermal equilibrium can support spontaneous currents and can be engineered to have unconventional transport properties. Here we report the emergence of (meta-)stable traveling bands in computer simulations of aligning circle swimmers. These bands are different from polar flocks and we show that they can be understood as non-dispersive soliton solutions of the underlying non-linear hydrodynamic equations with constant celerity (phase propagation speed) that is much larger than the propulsion speed. In contrast to solitons in passive media, these bands can induce a bulk particle current with a component perpendicular to the propagation direction, thus constituting a collective Hall (or Magnus) effect. Traveling bands require sufficiently small orbits and undergo a discontinuous transition into a synchronized state with transient polar clusters for large orbital radii.

Miniature robots provide unprecedented access to confined environments and show promising potential for novel applications such as search-and-rescue and high-value asset inspection. The capability of body deformation further enhances the reachability of these small robots in complex cluttered terrains similar to those of insects and soft arthropods. Motivated by this concept, we present CLARI, an insect-scale 2.59g quadrupedal robot capable of body deformation with tethered electrical connections for power and control and manufactured using laminate fabrication and assembled using origami pop-up techniques. In order to enable locomotion in multiple shape configurations, we designed a novel body architecture comprising of modular, actuated leg mechanisms. Overall, CLARI has eight independently actuated degrees of freedom (two per modular leg unit) driven by custom piezoelectric actuators, making it mechanically dextrous. We characterize open-loop robot locomotion at multiple stride frequencies (1-10Hz) using multiple gaits (trot, walk, etc.) in three different fixed body shapes (long, symmetric, wide) and illustrate the robot's capabilities. Finally, we demonstrate preliminary results of CLARI locomoting with a compliant body in open terrain and through a laterally constrained gap, a novel capability for legged robots. Our results represent the first step towards achieving effective cluttered terrain navigation with adaptable compliant robots in real-world environments.

For any two point sets $A,B \subset \mathbb{R}^d$ of size up to $n$, the Chamfer distance from $A$ to $B$ is defined as $\text{CH}(A,B)=\sum_{a \in A} \min_{b \in B} d_X(a,b)$, where $d_X$ is the underlying distance measure (e.g., the Euclidean or Manhattan distance). The Chamfer distance is a popular measure of dissimilarity between point clouds, used in many machine learning, computer vision, and graphics applications, and admits a straightforward $O(d n^2)$-time brute force algorithm. Further, the Chamfer distance is often used as a proxy for the more computationally demanding Earth-Mover (Optimal Transport) Distance. However, the \emph{quadratic} dependence on $n$ in the running time makes the naive approach intractable for large datasets. We overcome this bottleneck and present the first $(1+\epsilon)$-approximate algorithm for estimating the Chamfer distance with a near-linear running time. Specifically, our algorithm runs in time $O(nd \log (n)/\varepsilon^2)$ and is implementable. Our experiments demonstrate that it is both accurate and fast on large high-dimensional datasets. We believe that our algorithm will open new avenues for analyzing large high-dimensional point clouds. We also give evidence that if the goal is to \emph{report} a $(1+\varepsilon)$-approximate mapping from $A$ to $B$ (as opposed to just its value), then any sub-quadratic time algorithm is unlikely to exist.

Recurrent neural network-based reinforcement learning systems are capable of complex motor control tasks such as locomotion and manipulation, however, much of their underlying mechanisms still remain difficult to interpret. Our aim is to leverage computational neuroscience methodologies to understanding the population-level activity of robust robot locomotion controllers. Our investigation begins by analyzing topological structure, discovering that fragile controllers have a higher number of fixed points with unstable directions, resulting in poorer balance when instructed to stand in place. Next, we analyze the forced response of the system by applying targeted neural perturbations along directions of dominant population-level activity. We find evidence that recurrent state dynamics are structured and low-dimensional during walking, which aligns with primate studies. Additionally, when recurrent states are perturbed to zero, fragile agents continue to walk, which is indicative of a stronger reliance on sensory input and weaker recurrence.

Discrete and periodic contact switching is a key characteristic of steady-state legged locomotion. This paper introduces a framework for modeling and analyzing this contact-switching behavior through the framework of geometric mechanics on a toy robot model that can make continuous limb swings and discrete contact switches. The kinematics of this model form a hybrid shape-space and by extending the generalized Stokes' theorem to compute discrete curvature functions called \textit{stratified panels}, we determine average locomotion generated by gaits spanning multiple contact modes. Using this tool, we also demonstrate the ability to optimize gaits based on the system's locomotion constraints and perform gait reduction on a complex gait spanning multiple contact modes to highlight the method's scalability to multilegged systems., Comment: 7 pages, 6 figures, and link to associated video: "https://drive.google.com/file/d/12Sgl0R1oDLDWRrqlwwAt3JR2Gc3rEB4T/view?usp=sharing". Link to code: "https://github.com/Animal-Inspired-Motion-And-Robotics-Lab/Paper-Geometric-Mechanics-of-Contact-Switching-Systems". Accepted to RA-L on Monday, October 16th, 2023