Motivated by fast matrix multiplication and recent connections between asymptotic tensor rank and fine-grained complexity, we revisit classical tools from the matrix multiplication literature and develop a framework for obtaining improved asymptotic rank upper bounds for tensors beyond matrix multiplication. In the 1980s, Coppersmith-Winograd and Strassen discovered a series of speedup theorems for asymptotic rank: in certain regimes, one can extract additional terms from a border rank upper bound on a tensor T, and then use these terms to obtain an improved asymptotic rank of T. We establish general speedup theorems that subsume these results and enable quantitative improvements. Two representative applications are: 1) The asymptotic rank of the small Coppersmith-Winograd tensor cw_q is less than its border rank. For instance, we prove ̰{R}(cw₂) < 3.931, improving on ̲{R}(cw₂) = 4. It is known that ̰{R}(cw₂) = 3 would imply ω = 2. 2) A general improvement over Strassen’s bound: we obtain an upper bound below d^{2ω/3} on the asymptotic rank of any d× d× d tensor. To make full use of speedups, we analyze degenerations in which both sides are nontrivial direct sums, a setting where the optimal quantitative bound one can achieve was previously unclear. We do so via an approach we call Strassen calculus: a systematic method for converting such degeneration data into explicit asymptotic rank bounds using Strassen’s theory of the asymptotic spectrum.

We study circuits for computing linear transforms defined by Kronecker power matrices. The best-known (unbounded-depth) circuits, including the widely-applied fast Walsh-Hadamard transform and Yates’ algorithm, can be derived from the best-known depth- 2 circuits using known constructions, so we focus particularly on the depth- 2 case. Recent work [Jukna and Sergeev’13; Alman, STOC’21; Alman, Guan and Padaki, SODA’23; Sergeev’22] has improved on decades-old constructions in this area using a new rebalancing approach, but it was unclear how to apply this approach optimally, and the previous versions had complicated technical requirements.We find that Strassen’s theory of asymptotic spectra can be applied to capture the design of these circuits. This theory was designed to generalize the known techniques behind matrix multiplication algorithms as well as a variety of other algorithms with recursive structure, and it brings a number of new tools to use for designing depth- 2 circuits. In particular, in hindsight, we find that the techniques of recent work on rebalancing were proving special cases of the duality theorem which is central to Strassen’s theory. We carefully outline a collection of obstructions to designing small depth- 2 circuits using a rebalancing approach, and apply Strassen’s theory to show that our obstructions are complete.Using this connection, combined with other algorithmic techniques (including matrix rigidity upper bounds, constant-weight binary codes, and a “hole-fixing lemma” from recent matrix multiplication algorithms), we give new improved circuit constructions as well as other applications, including:•The $N \times N$ disjointness matrix has a depth-2 linear circuit of size $O\left(N^{1.2495}\right)$ over any field. This is the first construction which surpasses exponent 1.25, and thus yields smaller circuits for many families of matrices using reductions to disjointness, including all Kronecker products of $2 \times 2$ matrices, without using matrix rigidity upper bounds.•Barriers to further improvements, including that the Strong Exponential Time Hypothesis implies an $N^{1+\Omega(1)}$ size lower bound for depth-2 linear circuits computing the WalshHadamard transform (and the disjointness matrix with a technical caveat), and that proving such a $N^{1+\Omega(1)}$ depth2 size lower bound would imply breakthrough threshold circuit lower bounds.•The Orthogonal Vectors (OV) problem in moderate dimension d can be solved in deterministic time $\tilde{O}\left(n \cdot 1.155^{d}\right)$, derandomizing an algorithm of Nederlof and Wegrzycki [STOC’21], and the counting problem can be solved in time $\tilde{O}\left(n \cdot 1.26^{d}\right)$, improving an algorithm of Williams [FOCS’24] which runs in time $\tilde{O}\left(n \cdot 1.35^{d}\right)$. We design these new algorithms by noticing that prior algorithms for OV can be viewed as corresponding to depth- 2 circuits for the disjointness matrix, then using our framework for further improvements.

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.

The Transformer architecture is widely deployed in many popular and impactful Large Language Models. At its core is the attention mechanism for calculating correlations between pairs of tokens. Performing an attention computation takes quadratic time in the input size, and had become the time bottleneck for transformer operations. In order to circumvent this, researchers have used a variety of approaches, including designing heuristic algorithms for performing attention computations faster, and proposing alternatives to the attention mechanism which can be computed more quickly. For instance, state space models such as Mamba were designed to replace attention with an almost linear time alternative. In this paper, we prove that any such approach cannot perform important tasks that Transformer is able to perform (assuming a popular conjecture from fine-grained complexity theory). We focus on document similarity tasks, where one is given as input many documents and would like to find a pair which is (approximately) the most similar. We prove that Transformer is able to perform this task, and we prove that this task cannot be performed in truly subquadratic time by any algorithm. Thus, any model which can be evaluated in subquadratic time – whether because of subquadratic-time heuristics for attention, faster attention replacements like Mamba, or any other reason – cannot perform this task. In other words, in order to perform tasks that (implicitly or explicitly) involve document similarity, one may as well use Transformer and cannot avoid its quadratic running time.

Probabilistic polynomials over commutative rings offer a powerful way of representing Boolean functions. Although many degree lower bounds for such representations have been proved, sparsity lower bounds (counting the number of monomials in the polynomials) have not been so common. Sparsity upper bounds are of great interest for potential algorithmic applications, since sparse probabilistic polynomials are the key technical tool behind the best known algorithms for many core problems, including dense All-Pairs Shortest Paths, and the existence of sparser polynomials would lead to breakthrough algorithms for these problems. In this paper, we prove several strong lower bounds on the sparsity of probabilistic and approximate polynomials computing Boolean functions when 0 means "false". Our main result is that the AND of n ORs of c log n variables requires probabilistic polynomials (over any commutative ring which isn't too large) of sparsity n^Ω(log c) to achieve even 1/4 error. The lower bound is tight, and it rules out a large class of polynomial-method approaches for refuting the APSP and SETH conjectures via matrix multiplication. Our other results include: - Every probabilistic polynomial (over a commutative ring) for the disjointness function on two n-bit vectors requires exponential sparsity in order to achieve exponentially low error. - A generic lower bound that any function requiring probabilistic polynomials of degree d must require probabilistic polynomials of sparsity Ω(2^d). - Building on earlier work, we consider the probabilistic rank of Boolean functions which generalizes the notion of sparsity for probabilistic polynomials, and prove separations of probabilistic rank and probabilistic sparsity. Some of our results and lemmas are basis independent. For example, over any basis {a,b} for true and false where a ≠ b, and any commutative ring R, the AND function on n variables has no probabilistic R-polynomial with 2^o(n) sparsity, o(n) degree, and 1/2^o(n) error simultaneously. This AND lower bound is our main technical lemma used in the above lower bounds.

The quadratic complexity of self‑attention prevents transformers from scaling effectively to long input sequences. On the other hand, modern GPUs and other specialized hardware accelerators are well-optimized for processing small input sequences in transformers during both training and inference. A natural question arises: can we take advantage of the efficiency of small transformers to deal with long input sequences? In this paper, we show that transformers with long input sequences (large transformers) can be efficiently simulated by transformers that can only take short input sequences (small transformers). Specifically, we prove that any transformer with input length $N$ can be efficiently simulated by only $O((N/M)^2)$ transformers with input length $M \ll N$, and that this cannot be improved in the worst case. However, we then prove that in various natural scenarios including average-case inputs, sliding window masking and attention sinks, the optimal number $O(N/M)$ of small transformers suffice.

We present a new improvement on the laser method for designing fast matrix multiplication algorithms. The new method further develops the recent advances by [Duan, Wu, Zhou FOCS 2023] and [Vassilevska Williams, Xu, Xu, Zhou SODA 2024]. Surprisingly the new improvement is achieved by incorporating more asymmetry in the analysis, circumventing a fundamental tool of prior work that requires two of the three dimensions to be treated identically. The method yields a new bound on the square matrix multiplication exponent ω < 2.371339, improved from the previous bound of ω < 2.371552. We also improve the bounds of the exponents for multiplying rectangular matrices of various shapes.

Algebraic matrix multiplication algorithms are designed by bounding the rank of matrix multiplication tensors, and then using a recursive method. However, designing algorithms in this way quickly leads to large constant factors: if one proves that the tensor for multiplying n × n matrices has rank ≤ t, then the resulting recurrence shows that M × M matrices can be multiplied using O (n2 · Mlogn t) operations, where the leading constant scales proportionally to n2. Even modest increases in n can blow up the leading constant too much to be worth the slight decrease in the exponent of M. Meanwhile, the asymptotically best algorithms use very large n, such that n2 is larger than the number of atoms in the visible universe!

STOC ’25, Prague, Czechia

Abstract. For a matrix [Formula: see text] over a field [Formula: see text], its rank-[Formula: see text] rigidity, denoted by [Formula: see text], is the minimum Hamming distance from [Formula: see text] to a matrix of rank at most [Formula: see text] over [Formula: see text]. A central open challenge in complexity theory is to give explicit constructions of rigid matrices for a variety of parameter settings. In this work, building on Williams’ seminal connection between circuit-analysis algorithms and lower bounds [ J. ACM, 61 (2014), 2], we give a construction of rigid matrices in [Formula: see text]. Letting [Formula: see text] be a prime power, we show that there is an absolute constant [Formula: see text] such that, for all constants [Formula: see text], there is a [Formula: see text] machine [Formula: see text] such that, for infinitely many [Formula: see text]’s, [Formula: see text] outputs a matrix [Formula: see text] with [Formula: see text] over [Formula: see text]. Using known connections between matrix rigidity and other topics in complexity theory, we derive several consequences of our constructions, including that there is a function [Formula: see text] such that [Formula: see text]. Previously, it was open whether [Formula: see text]. For all [Formula: see text], there is a [Formula: see text] machine [Formula: see text] such that, for infinitely many [Formula: see text]’s, [Formula: see text] outputs an [Formula: see text] matrix [Formula: see text] whose linear transformation requires depth-2 [Formula: see text]-linear circuits of size [Formula: see text]. The previous best lower bound for an explicit family of [Formula: see text] matrices over [Formula: see text] was only [Formula: see text], for asymptotically good error correcting codes.

In the classical transformer attention scheme, we are given three $n \times d$ size matrices $Q, K, V$ (the query, key, and value tokens), and the goal is to compute a new $n \times d$ size matrix $D^{-1} \exp(QK^\top) V$ where $D = \mathrm{diag}( \exp(QK^\top) {\bf 1}_n )$. Here, $\exp()$ is applied entry-wise and ${\bf 1}_n$ denotes a length-$n$ vector whose entries are all ones. Intuitively, attention computation captures pairwise information between words in a sentence, but not higher-order information. Indeed, recent work \cite{sht23} has shown that attention units cannot solve simple problems about detecting triples of connected words. In this work, we study a generalization of attention which captures triple-wise correlations. The generalization is based on computations involving tensors defined by tuples of words. More formally, given five $n \times d$ size matrices $Q, K_1, K_2, V_1$ and $V_2$ (generalized query, key, and value tokens), our new goal is to compute an $n \times d$ size matrix $D^{-1} \exp( Q ( K_1 \oslash K_2)^\top ) (V_1 \oslash V_2) $ where $D = \mathrm{diag}( \exp( Q ( K_1 \oslash K_2)^\top ) {\bf 1}_{n^2} )$ and $K_1 \oslash K_2 \in \mathbb{R}^{n^2 \times d}$ denotes the column-wise Kronecker product of $K_1$ and $K_2$. This generalization is indeed able to solve problems about detecting triple-wise connections that were shown to be impossible for transformers. The potential downside of this generalization is that it appears as though computations are even more difficult, since the straightforward algorithm requires cubic time in $n$. However, we show that in the bounded-entry setting (which arises in practice, and which is well-studied in both theory and practice), there is actually a near-linear time algorithm. More precisely, we show that bounded entries are both necessary and sufficient for quickly performing generalized computations: $\bullet$ On the positive side, if all entries of the input matrices are bounded above by $o(\sqrt[3]{\log n})$ then we show how to approximate the ``tensor-type'' attention matrix in $n^{1+o(1)}$ time. $\bullet$ On the negative side, we show that if the entries of the input matrices may be as large as $\Omega(\sqrt[3]{\log n})$, then there is no algorithm that runs faster than $n^{3-o(1)}$ (assuming the Strong Exponential Time Hypothesis from fine-grained complexity theory). We also show that our construction, algorithms, and lower bounds naturally generalize to higher-order tensors and correlations. Interestingly, the higher the order of the tensors, the lower the bound on the entries needs to be for an efficient algorithm. Our results thus yield a natural tradeoff between the boundedness of the entries, and order of the tensor one may use for more expressive, efficient attention computation. Our constructions make use of a novel connection with a higher-order variant on the kernel density estimation problem. They combine a number of technical tools, including the polynomial method, algebraic geometry codes, and multiparty Merlin-Arthur communication protocols.

Generalizing work of Künnemann, Paturi, and Schneider [ICALP 2017], we study a wide class of high-dimensional dynamic programming (DP) problems in which one must find the shortest path between two points in a high-dimensional grid given a tensor of transition costs between nodes in the grid. This captures many classical problems which are solved using DP such as the knapsack problem, the airplane refueling problem, and the minimal-weight polygon triangulation problem. We observe that for many of these problems, the tensor naturally has low tensor rank or low slice rank. We then give new algorithms and a web of fine-grained reductions to tightly determine the complexity of these problems. For instance, we show that a polynomial speedup over the DP algorithm is possible when the tensor rank is a constant or the slice rank is 1, but that such a speedup is impossible if the tensor rank is slightly super-constant (assuming SETH) or the slice rank is at least 3 (assuming the APSP conjecture). We find that this characterizes the known complexities for many of these problems, and in some cases leads to new faster algorithms.

Large language models (LLMs) have made fundamental contributions over the last a few years. To train an LLM, one needs to alternatingly run `forward' computations and backward computations. The forward computation can be viewed as attention function evaluation, and the backward computation can be viewed as a gradient computation. In previous work by [Alman and Song, NeurIPS 2023], it was proved that the forward step can be performed in almost-linear time in certain parameter regimes, but that there is no truly sub-quadratic time algorithm in the remaining parameter regimes unless the popular hypothesis $\mathsf{SETH}$ is false. In this work, we show nearly identical results for the harder-seeming problem of computing the gradient of loss function of one layer attention network, and thus for the entire process of LLM training. This completely characterizes the fine-grained complexity of every step of LLM training.

We introduce a new linear-algebraic tool based on group representation theory, and use it to address three key problems in machine learning. 1. Past researchers have proposed fast attention algorithms for LLMs by approximating or replace softmax attention with other functions, such as low-degree polynomials. The key property of these functions is that, when applied entry-wise to the matrix $QK^{\top}$, the result is a low rank matrix when $Q$ and $K$ are $n \times d$ matrices and $n \gg d$. This suggests a natural question: what are all functions $f$ with this property? If other $f$ exist and are quickly computable, they can be used in place of softmax for fast subquadratic attention algorithms. It was previously known that low-degree polynomials have this property. We prove that low-degree polynomials are the only piecewise continuous functions with this property. This suggests that the low-rank fast attention only works for functions approximable by polynomials. Our work gives a converse to the polynomial method in algorithm design. 2. We prove the first full classification of all positive definite kernels that are functions of Manhattan or $\ell_1$ distance. Our work generalizes an existing theorem at the heart of all kernel methods in machine learning: the classification of all positive definite kernels that are functions of Euclidean distance. 3. The key problem in metric transforms, a mathematical theory used in geometry and machine learning, asks what functions transform pairwise distances in semi-metric space $M$ to semi-metric space $N$ for specified $M$ and $N$. We provide the first full classification of functions that transform Manhattan distances to Manhattan distances. Our work generalizes the foundational work of Schoenberg, which fully classifies functions that transform Euclidean to Euclidean distances. We additionally prove results about stable-rank preserving functions that are potentially useful in algorithmic design, and more. Our core new tool is called the representation theory of the hyperrectangle.

Suppose that S ⊆ [n]² contains no three points of the form (x,y), (x,y+δ), (x+δ,y'), where δ ≠ 0. How big can S be? Trivially, n ≤ |S| ≤ n². Slight improvements on these bounds are obtained from Shkredov’s upper bound for the corners problem [Shkredov, 2006], which shows that |S| ≤ O(n²/(log log n)^c) for some small c > 0, and a construction due to Petrov [Fedor Petrov, 2023], which shows that |S| ≥ Ω(n log n/√{log log n}). Could it be that for all ε > 0, |S| ≤ O(n^{1+ε})? We show that if so, this would rule out obtaining ω = 2 using a large family of abelian groups in the group-theoretic framework of [Cohn and Umans, 2003; Cohn et al., 2005] (which is known to capture the best bounds on ω to date), for which no barriers are currently known. Furthermore, an upper bound of O(n^{4/3 - ε}) for any fixed ε > 0 would rule out a conjectured approach to obtain ω = 2 of [Cohn et al., 2005]. Along the way, we encounter several problems that have much stronger constraints and that would already have these implications.

In the light bulb problem, one is given as input vectors $x_{1}, \ldots, x_{n}, y_{1}, \ldots, y_{n} \in\{-1,1\}^{d}$ which are all uniformly random. They are all chosen independently except for a planted pair $\left(x_{i^{*}}, y_{j^{*}}\right)$ which is chosen to have correlation $\rho$ for some constant $\rho\gt 0$. The goal is to find the planted pair. The light bulb problem was introduced over 30 years ago by L. Valiant, and is known to have many applications in data analysis, statistics, and learning theory. The naive algorithm runs in $\Omega\left(n^{2}\right)$ time, and algorithms based on Locality-Sensitive Hashing approach quadratic time as $\rho \rightarrow 0$. In 2012, G. Valiant gave a breakthrough algorithm running in time $O\left(n^{(5-\omega)} /(4-\omega)\right)\lt O\left(n^{1.615}\right)$, no matter how small $\rho\gt 0$ is, by making use of fast matrix multiplication. This was subsequently refined by Karppa, Kaski, and Kohonen in 2016 to running time $O\left(n^{2 \omega / 3}\right)\lt $ $O\left(n^{1.582}\right)$, but is essentially the only known approach for this important problem. In this paper, we propose a new approach based on replacing fast matrix multiplication with other variants and generalizations of matrix multiplication, which can be computed faster than matrix multiplication, but which may omit some terms one is supposed to compute, and include additional error terms. Our new approach can make use of a wide class of tensors which previously had no known algorithmic applications, including tensors which arise naturally as intermediate steps in border rank methods and in the Laser method. We further show that our approach can be combined with locality-sensitive hashing to design an algorithm whose running time improves as $\rho$ gets larger. To our knowledge, this is the first algorithm which combines fast matrix multiplication with hashing for the light bulb problem or any closest pair problem, and it leads to faster algorithms for small $\rho\gt 0$. We then focus on tensors for “multiplying“ $2 \times 2$ matrices; using such small tensors is typically required for practical algorithms. In this setting, the best prior algorithm, using Strassen’s algorithm for matrix multiplication, yields a running time of only $O\left(n^{1.872}\right)$. We introduce a new such low-rank tensor we call $T_{2112}$, which has omissions and errors compared to matrix multiplication, and using it, we design a new algorithm for the light bulb problem which runs in time $O\left(n^{1.797}\right)$. We also explain why we are optimistic that this approach could yield asymptotically faster algorithms for the light bulb problem.

In modern machine learning, inner product attention computation is a fundamental task for training large language models such as Transformer, GPT-1, BERT, GPT-2, GPT-3 and ChatGPT. Formally, in this problem, one is given as input three matrices $Q, K, V \in [-B,B]^{n \times d}$, and the goal is to construct the matrix $\mathrm{Att}(Q,K,V) := \mathrm{diag}(A {\bf 1}_n)^{-1} A V \in \mathbb{R}^{n \times d}$, where $A = \exp(QK^\top/d)$ is the `attention matrix', and $\exp$ is applied entry-wise. Straightforward methods for this problem explicitly compute the $n \times n$ attention matrix $A$, and hence require time $\Omega(n^2)$ even when $d = n^{o(1)}$ is small. In this paper, we investigate whether faster algorithms are possible by \emph{implicitly} making use of the matrix $A$. We present two results, showing that there is a sharp transition at $B = \Theta(\sqrt{\log n})$. $\bullet$ If $d = O(\log n)$ and $B = o(\sqrt{\log n})$, there is an $n^{1+o(1)}$ time algorithm to approximate $\mathrm{Att}(Q,K,V)$ up to $1/\mathrm{poly}(n)$ additive error. $\bullet$ If $d = O(\log n)$ and $B = \Theta (\sqrt{\log n})$, assuming the Strong Exponential Time Hypothesis from fine-grained complexity theory, it is impossible to approximate $\mathrm{Att}(Q,K,V)$ up to $1/\mathrm{poly}(n)$ additive error in truly subquadratic time $n^{2 - \Omega(1)}$. This gives a theoretical explanation for the phenomenon observed in practice that attention computation is much more efficient when the input matrices have smaller entries.

Over the last decade, deep neural networks have transformed our society, and they are already widely applied in various machine learning applications. State-of-the-art deep neural networks are becoming larger in size every year to deliver increasing model accuracy, and as a result, model training consumes substantial computing resources and will only consume more in the future. Using current training methods, in each iteration, to process a data point $x \in \mathbb{R}^d$ in a layer, we need to spend $\Theta(md)$ time to evaluate all the $m$ neurons in the layer. This means processing the entire layer takes $\Theta(nmd)$ time for $n$ data points. Recent work [Song, Yang and Zhang, NeurIPS 2021] reduces this time per iteration to $o(nmd)$, but requires exponential time to preprocess either the data or the neural network weights, making it unlikely to have practical usage. In this work, we present a new preprocessing method that simply stores the weight-data correlation in a tree data structure in order to quickly and dynamically detect which neurons fire at each iteration. Our method requires only $O(nmd)$ time in preprocessing and still achieves $o(nmd)$ time per iteration. We complement our new algorithm with a lower bound, proving that assuming a popular conjecture from complexity theory, one could not substantially speed up our algorithm for dynamic detection of firing neurons.

A linear circuit for computing an N × N matrix M is a circuit with N inputs corresponding to the entries of a vector x and N outputs corresponding to the entries of the transformed vector Mx, and where each gate computes a linear combination of its inputs. Each gate may have unbounded fan-in, and the size of the circuit is the number of wires. This model captures most known algorithms for computing linear transforms, and (in the constant-depth or 'synchronous' settings) is equivalent to factoring M as the product of sparse matrices. We give new, smaller constructions of constant-depth linear circuits for computing any matrix which is the Kronecker power of a fixed matrix. A standard argument (e.g., the mixed product property of Kronecker products, or a generalization of the Fast Walsh-Hadamard transform) shows that any such N × N matrix has a depth-2 circuit of size O(N1.5). We improve on this for all such matrices, and especially for some such matrices of particular interest: • For any integer q > 1 and any matrix which is the Kronecker power of a fixed q × q matrix, we construct a depth-2 circuit of size O(N1.5-aq), where aq > 0 is a positive constant depending only on q. No bound beating size O(N1.5) was previously known for any q > 2. • For the case q = 2, i.e., for any matrix which is the Kronecker power of a fixed 2 × 2 matrix, we construct a depth-2 circuit of size O(N1.446), improving the prior best size O(N1.493) [Alman, 2021]. • For the Walsh-Hadamard transform, we construct a depth-2 circuit of size O(N1.443), improving the prior best size O(N1.476) [Alman, 2021]. • For the disjointness matrix (the communication matrix of set disjointness, or equivalently, the matrix for the linear transform that evaluates a multilinear polynomial on all 0/1 inputs), we construct a depth-2 circuit of size O(N1.258), improving the prior best size O(N1.272) [Jukna and Sergeev, 2013]. Our constructions also generalize to improving the standard construction for any depth ≤ O (log N). Our main technical tool is an improved way to convert a nontrivial circuit for any matrix into a circuit for its Kronecker powers. Our new bounds provably could not be achieved using the approaches of prior work.

We give algorithms with lower arithmetic operation counts for both the Walsh-Hadamard Transform (WHT) and the Discrete Fourier Transform (DFT) on inputs of power-of-2 size N.

We study the known techniques for designing Matrix Multiplication algorithms. The two main approaches are the Laser method of Strassen, and the group theoretic approach of Cohn and Umans. We define a generalization based on zeroing outs which subsumes these two approaches, which we call the Solar method, and an even more general method based on monomial degenerations, which we call the Galactic method. We then design a suite of techniques for proving lower bounds on the value of $\omega$, the exponent of matrix multiplication, which can be achieved by algorithms using many tensors $T$ and the Galactic method. Some of our techniques exploit “local” properties of $T$, like finding a subtensor of $T$ which is so “weak” that $T$ itself couldn't be used to achieve a good bound on $\omega$, while others exploit “global” properties, like $T$ being a monomial degeneration of the structural tensor of a group algebra. Our main result is that there is a universal constant $\ell>2$ such that a large class of tensors generalizing the Coppersmith--Winograd tensor $CW_q$ cannot be used within the Galactic method to show a bound on $\omega$ better than $\ell$ for any $q$. We give evidence that previous lower-bounding techniques were not strong enough to show this. We also prove a number of complementary results along the way, including that for any group $G$, the structural tensor of $\C[G]$ can be used to recover the best bound on $\omega$ which the Coppersmith--Winograd approach gets using $CW_{|G|-2}$ as long as the asymptotic rank of the structural tensor is not too large.

For any real numbers $B \ge 1$ and $δ\in (0, 1)$ and function $f: [0, B] \rightarrow \mathbb{R}$, let $d_{B; δ} (f) \in \mathbb{Z}_{> 0}$ denote the minimum degree of a polynomial $p(x)$ satisfying $\sup_{x \in [0, B]} \big| p(x) - f(x) \big| < δ$. In this paper, we provide precise asymptotics for $d_{B; δ} (e^{-x})$ and $d_{B; δ} (e^{x})$ in terms of both $B$ and $δ$, improving both the previously known upper bounds and lower bounds. In particular, we show $$d_{B; δ} (e^{-x}) = Θ\left( \max \left\{ \sqrt{B \log(δ^{-1})}, \frac{\log(δ^{-1}) }{ \log(B^{-1} \log(δ^{-1}))} \right\}\right), \text{ and}$$ $$d_{B; δ} (e^{x}) = Θ\left( \max \left\{ B, \frac{\log(δ^{-1}) }{ \log(B^{-1} \log(δ^{-1}))} \right\}\right).$$ Polynomial approximations for $e^{-x}$ and $e^x$ have applications to the design of algorithms for many problems, and our degree bounds show both the power and limitations of these algorithms. We focus in particular on the Batch Gaussian Kernel Density Estimation problem for $n$ sample points in $Θ(\log n)$ dimensions with error $δ= n^{-Θ(1)}$. We show that the running time one can achieve depends on the square of the diameter of the point set, $B$, with a transition at $B = Θ(\log n)$ mirroring the corresponding transition in $d_{B; δ} (e^{-x})$: - When $B=o(\log n)$, we give the first algorithm running in time $n^{1 + o(1)}$. - When $B = κ\log n$ for a small constant $κ>0$, we give an algorithm running in time $n^{1 + O(\log \log κ^{-1} /\log κ^{-1})}$. The $\log \log κ^{-1} /\log κ^{-1}$ term in the exponent comes from analyzing the behavior of the leading constant in our computation of $d_{B; δ} (e^{-x})$. - When $B = ω(\log n)$, we show that time $n^{2 - o(1)}$ is necessary assuming SETH.

We design the first efficient sensitivity oracles and dynamic algorithms for a variety of parameterized problems. Our main approach is to modify the algebraic coding technique from static parameterized algorithm design, which had not previously been used in a dynamic context. We particularly build off of the `extensor coding' method of Brand, Dell and Husfeldt [STOC'18], employing properties of the exterior algebra over different fields. For the $k$-Path detection problem for directed graphs, it is known that no efficient dynamic algorithm exists (under popular assumptions from fine-grained complexity). We circumvent this by designing an efficient sensitivity oracle, which preprocesses a directed graph on $n$ vertices in $2^k poly(k) n^{ω+o(1)}$ time, such that, given $\ell$ updates (mixing edge insertions and deletions, and vertex deletions) to that input graph, it can decide in time $\ell^2 2^kpoly(k)$ and with high probability, whether the updated graph contains a path of length $k$. We also give a deterministic sensitivity oracle requiring $4^k poly(k) n^{ω+o(1)}$ preprocessing time and $\ell^2 2^{ωk + o(k)}$ query time, and obtain a randomized sensitivity oracle for the task of approximately counting the number of $k$-paths. For $k$-Path detection in undirected graphs, we obtain a randomized sensitivity oracle with $O(1.66^k n^3)$ preprocessing time and $O(\ell^3 1.66^k)$ query time, and a better bound for undirected bipartite graphs. In addition, we present the first fully dynamic algorithms for a variety of problems: $k$-Partial Cover, $m$-Set $k$-Packing, $t$-Dominating Set, $d$-Dimensional $k$-Matching, and Exact $k$-Partial Cover. For example, for $k$-Partial Cover we show a randomized dynamic algorithm with $2^k poly(k)polylog(n)$ update time, and a deterministic dynamic algorithm with $4^kpoly(k)polylog(n)$ update time.

The complexity of matrix multiplication is measured in terms of ω, the smallest real number such that two n × n matrices can be multiplied using O(nω+∊) field operations for all ∊ > 0; the best bound until now is ω < 2.37287 [Le Gall'14]. All bounds on ω since 1986 have been obtained using the so-called laser method, a way to lower-bound the ‘value’ of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on ω, and we indeed obtain the best bound on ω to date: ω < 2.37286. The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity.

For a matrix M and a positive integer r, the rank r rigidity of M is the smallest number of entries of M which one must change to make its rank at most r. There are many known applications of rigidity lower bounds to a variety of areas in complexity theory, but fewer known applications of rigidity upper bounds. In this paper, we use rigidity upper bounds to prove new upper bounds in a few different models of computation. Our results include:

For a function K: Rd× Rd→ R≥0, and a set P = {x1,..., xn} ⊂ Rdof n points, the K graph GP of P is the complete graph on n nodes where the weight between nodes i and j is given by K(xi, xj). In this paper, we initiate the study of when efficient spectral graph theory is possible on these graphs. We investigate whether or not it is possible to solve the following problems in n1+o(1)time for a K-graph GP when : (a) Multiply a given vector by the adjacency matrix or Laplacian matrix of GP (b) Find a spectral sparsifier of GP (c) Solve a Laplacian system in GP's Laplacian matrix For each of these problems, we consider all functions of the form K(u, v)=f(||u-v||22) for a function f: R→ R. We provide algorithms and comparable hardness results for many such K, including the Gaussian kernel, Neural tangent kernels, and more. For example, in dimension d=Ω(logn), we show that there is a parameter associated with the function f for which low parameter values imply n1+o(1)time algorithms for all three of these problems and high parameter values imply the nonexistence of subquadratic time algorithms assuming Strong Exponential Time Hypothesis (SETH), given natural assumptions on f. As part of our results, we also show that the exponential dependence on the dimension d in the celebrated fast multi-pole method of Greengard and Rokhlin cannot be improved, assuming SETH, for a broad class of functions f. To the best of our knowledge, this is the first formal limitation proven about fast multipole methods.

A graph G on n nodes is an Orthogonal Vectors (OV) graph of dimension d if there are vectors v_1, …, v_n ∈ {0,1}^d such that nodes i and j are adjacent in G if and only if ⟨v_i,v_j⟩ = 0 over Z. In this paper, we study a number of basic graph algorithm problems, except where one is given as input the vectors defining an OV graph instead of a general graph. We show that for each of the following problems, an algorithm solving it faster on such OV graphs G of dimension only d=O(log n) than in the general case would refute a plausible conjecture about the time required to solve sparse MAX-k-SAT instances: - Determining whether G contains a triangle. - More generally, determining whether G contains a directed k-cycle for any k ≥ 3. - Computing the square of the adjacency matrix of G over ℤ or ?_2. - Maintaining the shortest distance between two fixed nodes of G, or whether G has a perfect matching, when G is a dynamically updating OV graph. We also prove some complementary results about OV graphs. We show that any problem which is NP-hard on constant-degree graphs is also NP-hard on OV graphs of dimension O(log n), and we give two problems which can be solved faster on OV graphs than in general: Maximum Clique, and Online Matrix-Vector Multiplication.

We present a deterministic, truly subquadratic algorithm for offline (1 + ε)-approximate nearest or farthest neighbor search (in particular, the closest pair or diameter problem) in Hamming space in any dimension d ≤ nδ, for a sufficiently small constant δ > 0. The running time of the algorithm is roughly for nearest neighbors, or for farthest. The algorithm follows from a simple combination of expander walks, Chebyshev polynomials, and rectangular matrix multiplication. We also show how to eliminate errors in the previous Monte Carlo randomized algorithm of Alman, Chan, and Williams [FOCS’16] for offline approximate nearest or farthest neighbors, and obtain a Las Vegas randomized algorithm with expected running time . Finally, we note a simplification of Alman, Chan, and Williams' method and obtain a slightly improved Monte Carlo randomized algorithm with running time . As one application, we obtain improved deterministic and randomized (1 + ε)-approximation algorithms for MAX-SAT.

In this paper, we present a new algorithm for maintaining linear sketches in turnstile streams with faster update time. As an application, we show that log n Count sketches or CountMin sketches with a constant number of columns (i.e., buckets) can be implicitly maintained in worst-case O(log0.582 n) update time using O(log n) words of space, on a standard word RAM with word-size w = Θ(log n). The exponent 0.582 ≈ 2ω/3 – 1, where ω is the current matrix multiplication exponent. Due to the numerous applications of linear sketches, our algorithm improves the update time for many streaming problems in turnstile streams, in the high success probability setting, without using more space, including ℓ2 norm estimation, ℓ2 heavy hitters, point query with ℓ1 or ℓ2 error, etc. Our algorithm generalizes, with the same update time and space, to maintaining log n linear sketches, where each sketch partitions the coordinates into k < logo(l) n buckets using a c-wise independent hash function for constant c, maintains the sum of coordinates for each bucket. Moreover, if arbitrary word operations are allowed, the update time can be further improved to O(log0.187 n), where 0.187 ≈ ω/2 – 1. Our update algorithm is adaptive, and it circumvents the non-adaptive cell-probe lower bounds for turnstile streaming algorithms by Larsen, Nelson and Nguyên (STOC’15). On the other hand, our result also shows that proving unconditional cell-probe lower bound for the update time seems very difficult, even if the space is restricted to be (nearly) the optimum. If ω = 2, the cell-probe update time of our algorithm would be logo(l) n. Hence, proving any higher lower bound would imply ω > 2.

Fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet so far those algorithms have been largely restricted to static inputs. In this article, we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems that are known to have f ( k ) n 1+o(1) time algorithms on inputs of size n , and we consider the question of whether there is a data structure that supports small updates (such as edge/vertex/set/element insertions and deletions) with an update time of g ( k ) n o(1) ; such an update time would be essentially optimal. Update and query times independent of n are particularly desirable. Among many other results, we show that F EEDBACK V ERTEX S ET and k -P ATH admit dynamic algorithms with f ( k )log O(1) update and query times for some function f depending on the solution size k only. We complement our positive results by several conditional and unconditional lower bounds. For example, we show that unlike their undirected counterparts, D IRECTED F EEDBACK V ERTEX S ET and D IRECTED k -P ATH do not admit dynamic algorithms with n o(1) update and query times even for constant solution sizes k ≤ 3 , assuming popular hardness hypotheses. We also show that unconditionally, in the cell probe model, D IRECTED F EEDBACK V ERTEX S ET cannot be solved with update time that is purely a function of k .

For a matrix H over a field F, its rank-r rigidity, denoted R_H (r), is the minimum Hamming distance from H to a matrix of rank at most r over F. A central open challenge in complexity theory is to give explicit constructions of rigid matrices for a variety of parameter settings. In this work, building on Williams' seminal connection between circuit-analysis algorithms and lower bounds [Williams, J. ACM 2014], we give a construction of rigid matrices in P^NP. Letting q = p^r be a prime power, we show: • There is an absolute constant δ>0 such that, for all constants ε >0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs a matrix H_N ∊ {0,1}^N×N with R_H_N (2^ (log N)^ 1/4-ε) ≥ δ ⋅ N^2 over F_q. Using known connections between matrix rigidity and other topics in complexity theory, we derive several consequences of our constructions, including: • There is a function f ∊ TIME [2^ (log n)^ ω(1)]^ NP such that f ∉ PH^cc. Previously, it was open whether E^NP ⊂ PH^cc. • For all ε >0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs an N × N matrix H_N ∊ {0,1}^N×N whose linear transformation requires depth-2 F_q-linear circuits of size Ω(N ⋅ 2^ (log N)^ 1/4 - ε). The previous best lower bound for an explicit family of N × N matrices over F_q was only Ω(N log^2 N / (log log N)^2), for asymptotically good error-correcting codes.

We study the known techniques for designing Matrix Multiplication algorithms. The two main approaches are the Laser method of Strassen, and the Group theoretic approach of Cohn and Umans. We define a generalization based on zeroing outs which subsumes these two approaches, which we call the Solar method, and an even more general method based on monomial degenerations, which we call the Galactic method. We then design a suite of techniques for proving lower bounds on the value of omega, the exponent of matrix multiplication, which can be achieved by algorithms using many tensors T and the Galactic method. Some of our techniques exploit 'local' properties of T, like finding a sub-tensor of T which is so 'weak' that T itself couldn't be used to achieve a good bound on omega, while others exploit 'global' properties, like T being a monomial degeneration of the structural tensor of a group algebra. Our main result is that there is a universal constant ℓ>2 such that a large class of tensors generalizing the Coppersmith-Winograd tensor CW_q cannot be used within the Galactic method to show a bound on omega better than ell, for any q. We give evidence that previous lower-bounding techniques were not strong enough to show this. We also prove a number of complementary results along the way, including that for any group G, the structural tensor of C[G] can be used to recover the best bound on omega which the Coppersmith-Winograd approach gets using CW_|G|-2 as long as the asymptotic rank of the structural tensor is not too large.

We consider the techniques behind the current best algorithms for matrix multiplication. Our results are threefold. (1) We provide a unifying framework, showing that all known matrix multiplication running times since 1986 can be achieved from a single very natural tensor - the structural tensor $T_q$ of addition modulo an integer $q$. (2) We show that if one applies a generalization of the known techniques (arbitrary zeroing out of tensor powers to obtain independent matrix products in order to use the asymptotic sum inequality of Schönhage) to an arbitrary monomial degeneration of $T_q$, then there is an explicit lower bound, depending on $q$, on the bound on the matrix multiplication exponent $ω$ that one can achieve. We also show upper bounds on the value $α$ that one can achieve, where $α$ is such that $n\times n^α\times n$ matrix multiplication can be computed in $n^{2+o(1)}$ time. (3) We show that our lower bound on $ω$ approaches $2$ as $q$ goes to infinity. This suggests a promising approach to improving the bound on $ω$: for variable $q$, find a monomial degeneration of $T_q$ which, using the known techniques, produces an upper bound on $ω$ as a function of $q$. Then, take $q$ to infinity. It is not ruled out, and hence possible, that one can obtain $ω=2$ in this way.

In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players, Bob, his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result each time before the next piece is revealed to Bob. This model has a closer and more natural correspondence to dynamic data structures than classic communication models do, and hence presents a new perspective on data structures.

Fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet, so far those algorithms have been largely restricted to static inputs. In this paper we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems which are known to have f(k)n^{1+o(1)} time algorithms on inputs of size n, and we consider the question of whether there is a data structure that supports small updates (such as edge/vertex/set/element insertions and deletions) with an update time of g(k)n^{o(1)}; such an update time would be essentially optimal. Update and query times independent of n are particularly desirable. Among many other results, we show that Feedback Vertex Set and k-Path admit dynamic algorithms with f(k)log O(1) n update and query times for some function f depending on the solution size k only. We complement our positive results by several conditional and unconditional lower bounds. For example, we show that unlike their undirected counterparts, Directed Feedback Vertex Set and Directed k-Path do not admit dynamic algorithms with n^{o(1) } update and query times even for constant solution sizes k <= 3, assuming popular hardness hypotheses. We also show that unconditionally, in the cell probe model, Directed Feedback Vertex Set cannot be solved with update time that is purely a function of k.

We consider a notion of probabilistic rank and probabilistic sign-rank of a matrix, which measure the extent to which a matrix can be probabilistically represented by low-rank matrices. We demonstrate several connections with matrix rigidity, communication complexity, and circuit lower bounds. The most interesting outcomes are:

We design new polynomials for representing threshold functions in three different regimes: probabilistic polynomials of low degree, which need far less randomness than previous constructions, polynomial threshold functions (PTFs) with "nice" threshold behavior and degree almost as low as the probabilistic polynomials, and a new notion of probabilistic PTFs where we combine the above techniques to achieve even lower degree with similar "nice" threshold behavior. Utilizing these polynomial constructions, we design faster algorithms for a variety of problems: · Offline Hamming Nearest (and Furthest) Neighbors: Given n red and n blue points in d-dimensional Hamming space for d = c log n, we can find an (exact) nearest (or furthest) blue neighbor for every red point in randomized time n2-1/O(√clog2/3c) or deterministic time n2-1/O(c log2 c). These improve on a randomized n2-1/O(c log2 c)bound by Alman and Williams (FOCS'15), and also lead to faster MAX-SAT algorithms for sparse CNFs. · Offline Approximate Nearest (and Furthest) Neighbors: Given n red and n blue points in d-dimensional ℓ1or Euclidean space, we can find a (1+ε)-approximate nearest (or furthest) blue neighbor for each red point in randomized time near dn+n2-Ω(ε1/3/log(1/ε)). This improves on an algorithm by Valiant (FOCS'12) with randomized time near dn+n2-Ω(√ε), which in turn improves previous methods based on locality-sensitive hashing. · SAT Algorithms and Lower Bounds for Circuits With Linear Threshold Functions: We give a satisfiability algorithm for AC0[m] o LTF LTF circuits with a subquadratic number of LTF gates on the bottom layer, and a subexponential number of gates on the other layers, that runs in deterministic 2n-nεtime. This strictly generalizes a SAT algorithm for ACC0oLTF circuits of subexponential size by Williams (STOC'14) and also implies new circuit lower bounds for threshold circuits, improving a recent gate lower bound of Kane and Williams (STOC'16). We also give a randomized 2n-nε-time SAT algorithm for subexponential-size MAJ o AC0oLTF o AC0oLTF circuits, where the top MAJ gate and middle LTF gates have O(n6/5-δ) fan-in.

We show how to compute any symmetric Boolean function on n variables over any field (as well as '/ the integers) with a probabilistic polynomial of degree O( √nlog(1/ε)) and error at most ε. The degree dependence on n and ε is optimal, matching a lower bound of Razborov (1987) and Smolensky (1987) for the MAJORITY function. The proof is constructive: a low-degree polynomial can be efficiently sampled from the distribution. This polynomial construction is combined with other algebraic ideas to give the first subquadratic time algorithm for computing a (worst-case) batch of Hamming distances in superlogarithmic dimensions, exactly. To illustrate, let c(n) : ℕ → ℕ. Suppose we are given a database D of n vectors in {0,1}c(n)lognand a collection of n query vectors Q in the same dimension. For all u ∈ Q, we wish to compute a v ∈ D with minimum Hamming distance from u. We solve this problem in n2-1/O(c(n)log2c(n))randomized time. Hence, the problem is in “truly subquadratic” time for O(logn) dimensions, and in subquadratic time for d = o((log2 n)/(loglogn)2). We apply the algorithm to computing pairs with maximum inner product, closest pair in ℓ1 for vectors with bounded integer entries, and pairs with maximum Jaccard coefficients.