Given a matrix $ A\in\mathbb {R}^{n\times d} $ and a vector $ b\in\mathbb {R}^ n $, we
consider the regression problem with $\ell_\infty $ guarantees: finding a vector …

Attention mechanism is the key to large language models, and attention matrix serves as an
algorithmic and computational bottleneck for such a scheme. In this paper, we define two …

Since 2008, after the proposal of a Bitcoin electronic cash system, Bitcoin has fundamentally
changed the economic system over the last decade. Since 2022, large language models …

Matrix sensing is a problem in signal processing and machine learning that involves
recovering a low-rank matrix from a set of linear measurements. The goal is to reconstruct …

Adversarial training is a widely used strategy for making neural networks resistant to
adversarial perturbations. For a neural network of width $ m $, $ n $ input training data in $ d …

Large language models (LLMs) have shown their power in different areas. Attention
computation, as an important subroutine of LLMs, has also attracted interests in theory …

Submodular functions have many real-world applications, such as document summarization,
sensor placement, and image segmentation. For all these applications, the key building …

In this paper, we study the problem of speeding up a type of optimization algorithms called
Frank-Wolfe, a conditional gradient method. We develop and employ two novel inner …

In this paper, we propose Adam-Hash: an adaptive and dynamic multi-resolution hashing
data-structure for fast pairwise summation estimation. Given a data-set X⊂ ℝ d, a binary …

Abstract In the\emph {Distance Oracle} problem, the goal is to preprocess $ n $ vectors $
x_1, x_2,\cdots, x_n $ in a $ d $-dimensional normed space $(\mathbb {X}^ d,\|\cdot\| _l) …