Transformers, especially the decoder-only variants, are the backbone of most modern large language models. Yet, we have a very limited understanding of their limitations (i.e., what tasks they cannot solve) besides the simplest 1-layer case. Due to the difficulty of analyzing multi-layer models, all previous work relies on unproven complexity conjectures to show limitations for multi-layer Transformers. In this work, we prove the first unconditional lower bound against multilayer decoder-only transformers. For any constant L, we prove that any L-layer decoder-only transformer needs a polynomial model dimension $\left(n^{\Omega(1)}\right)$ to perform sequential composition of L functions over an input of n tokens. As a consequence, our results give: (1) the first depthwidth trade-off for multi-layer transformers, exhibiting that the L-step composition task is exponentially harder for L-layer models compared to $(L+1)$-layer ones; (2) an unconditional separation between encoder and decoder, exhibiting a hard task for decoders that can be solved by an exponentially shallower and smaller encoder; (3) a provable advantage of chain-of-thought, exhibiting a task that becomes exponentially easier when the model is allowed to produce an intermediate sequence of tokens before outputting the final answer. On the technical side, we propose the multi-party autoregressive communication model that abstracts the key aspects of a decoder-only Transformer. In particular, lower bounds within this communication model imply lower bounds against decoder-only transformers, independent of their implementation details. To prove lower bounds in this communication model, we also introduce a new proof technique that finds a certain indistinguishable decomposition of all possible inputs iteratively. We believe our new communication model and proof techniques will be helpful to understand the computational power of transformers further.

Beam hopping (BH) has emerged as a critical solution for interference mitigation in mega-constellation satellite networks. Traditional ground-based centralized beam scheduling methods become infeasible in mega-constellations due to prohibitive computational complexity and inadequate responsiveness to bursty traffic demands. Given the non-convex and NP-hard nature of the multi-satellite BH optimization problem, we strategically decompose it into two subproblems. Hence the two-stage on-board BH method based on collaborative satellite clusters is proposed in this paper to address the challenges for efficient BH scheduling. The pre-activated cell selection stage is designed with a mechanism for dynamic updating of cell pre-activation probability to maximize the system throughput. In the cell-satellite matching stage, load balancing across satellites is achieved by minimizing inter-satellite load disparities. Simulation results show that the average throughput could be improved by over 10% compared to the baseline. Moreover, the difference in load between satellites is significantly reduced by 26.38%.

Computing the approximate quantiles or ranks of a stream is a fundamental task in data monitoring. Given a stream of elements x1,x2,. ..,xn and a query x, a relative-error quantile estimation algorithm can estimate the rank of x with respect to the stream, up to a multiplicative ±∈ · rank(x ) error. Notably, this requires the sketch to obtain more precise estimates for the ranks of elements on the tails of the distribution, as compared to the additive ±en error regime. This is particularly favorable for some practical applications, such as anomaly detection.

Estimating quantiles is one of the foundational problems of data sketching. Given$n$elements$x_{1},x_{2}, \ldots, x_{n}$from some universe of size$U$arriving in a data stream, a quantile sketch estimates the rank of any element with additive error at most$\varepsilon n$. A low-space algorithm solving this task has applications in database systems, network measurement, load balancing, and many other practical scenarios. Current quantile estimation algorithms described as optimal include the GK sketch (Greenwald and Khanna 2001) using$O(\varepsilon^{-1}\log n)$words (deterministic) and the KLL sketch (Karnin, Lang, and Liberty 2016) using$O (>\varepsilon$log log$(1/\delta)$) words (ran-domized, with failure probability$\delta$). However, both algorithms are only optimal in the comparison-based model, whereas many typical applications involve streams of integers that the sketch can use aside from making comparisons. If we go beyond the comparison-based model, the deterministic q-digest sketch (Shrivastava, Buragohain, Agrawal, and Suri 2004) achieves a space complexity of$O(\varepsilon^{-1}\log U)$words, which is incomparable to the previously-mentioned sketches. It has long been asked whether there is a quantile sketch using$O(\epsilon^{-1})$words of space (which is optimal as long as$n\leq$poly$(U)$). In this work, we present a deterministic algorithm using$O(\varepsilon^{-1})$words, resolving this line of work.

The classical prophet inequalities problem introduced by Krengel and Sucheston [1977, 1978] assumed complete knowledge of distributions. However, such an assumption may be unrealistic both in practice and for some applications.

We consider the following well studied problem of metric distortion in social choice. Suppose we have an election with n voters and m candidates who lie in a shared metric space. We would like to design a voting rule that chooses a candidate whose average distance to the voters is small. However, instead of having direct access to the distances in the metric space, each voter gives us a ranked list of the candidates in order of distance. Can we design a rule that regardless of the election instance and underlying metric space, chooses a candidate whose cost differs from the true optimum by only a small factor (known as the distortion)?

We study the cost of parallelizing weak-to-strong boosting algorithms for learning, following the recent work of Karbasi and Larsen. Our main results are two-fold:•First, we prove a tight lower bound, showing that even “slight” parallelization of boosting requires an exponential blow-up in the complexity of training.Specifically, let γ be the weak learner's advantage over random guessing. The famous AdaBoost algorithm produces an accurate hypothesis by interacting with the weak learner for Õ(1/γ2)1 rounds where each round runs in polynomial time.Karbasi and Larsen showed that “significant” parallelization must incur exponential blow-up: Any boosting algorithm either interacts with the weak learner for Ω(1/γ) rounds or incurs an exp(d/γ) blow-up in the complexity of training, where d is the VC dimension of the hypothesis class. We close the gap by showing that any boosting algorithm either has Ω(1/γ2) rounds of interaction or incurs a smaller exponential blow-up of exp(d).•Complementing our lower bound, we show that there exists a boosting algorithm using Õ(1/(tγ2)) rounds, and only suffer a blow-up of exp(d · t2).Plugging in t = ω(1), this shows that the smaller blow-up in our lower bound is tight. More interestingly, this provides the first trade-off between the parallelism and the total work required for boosting.

We consider the following well-studied problem of metric distortion in social choice. Suppose that we have an election with n voters and m candidates located in a shared metric space. We would like to design a voting rule that chooses a candidate whose average distance to the voters is small. However, instead of having direct access to the distances in the metric space, the voting rule obtains, from each voter, a ranked list of the candidates in order of distance. Can we design a rule that, regardless of the election instance and underlying metric space, chooses a candidate whose cost differs from the true optimum by only a small factor (known as the distortion )? A long line of work culminated in finding optimal deterministic voting rules with metric distortion 3. However, for randomized voting rules, there is still a significant gap in our understanding: even though the best lower bound is substantially lower at 2.112, the best upper bound is still 3, which is attained even by simple rules such as Random Dictatorship. Finding a randomized rule that guarantees distortion 3 - ɛ for some constant ɛ has been a major challenge in computational social choice, as prevalent approaches to designing voting rules are known to be insufficient. In particular, such a voting rule must use information beyond aggregate comparisons between pairs of candidates, and cannot only assign positive probability to candidates that are voters’ top choices. In this work, we give a rule that guarantees distortion less than 2.753. To do so, we study a handful of voting rules that are new to the problem. One is Maximal Lotteries , a rule based on the Nash equilibrium of a natural zero-sum game that dates back to the 1960s. The others are novel rules that can be thought of as hybrids of Random Dictatorship and the Copeland rule. None of these rules can beat distortion 3 alone; however, a careful randomization between Maximal Lotteries and any of the novel rules can.

Estimating the ε-approximate quantiles or ranks of a stream is a fundamental task in data monitoring. Given a stream x_1,..., x_n from a universe \mathcalU with total order, an additive-error quantile sketch \mathcalM allows us to approximate the rank of any query y\in \mathcalU up to additive ε n error. In 2001, Greenwald and Khanna gave a deterministic algorithm (GK sketch) that solves the ε-approximate quantiles estimation problem using O(ε^-1 łog(ε n)) space \citegreenwald2001space ; recently, this algorithm was shown to be optimal by Cormode and Vesleý in 2020 \citecormode2020tight. However, due to the intricacy of the GK sketch and its analysis, over-simplified versions of the algorithm are implemented in practical applications, often without any known theoretical guarantees. In fact, it has remained an open question whether the GK sketch can be simplified while maintaining the optimal space bound. In this paper, we resolve this open question by giving a simplified deterministic algorithm that stores at most (2 + o(1))ε^-1 łog (ε n) elements and solves the additive-error quantile estimation problem; as a side benefit, our algorithm achieves a smaller constant factor than the \frac11 2 ε^-1 łog(ε n) space bound in the original GK sketch~\citegreenwald2001space. Our algorithm features an easier analysis and still achieves the same optimal asymptotic space complexity as the original GK sketch. Lastly, our simplification enables an efficient data structure implementation, with a worst-case runtime of O(łog(1/ε) + łog łog (ε n)) per-element for the ordinary ε-approximate quantile estimation problem. Also, for the related "weighted'' quantile estimation problem, we give efficient data structures for our simplified algorithm which guarantee a worst-case per-element runtime of O(łog(1/ε) + łog łog (ε W_n/w_\textrmmin )), achieving an improvement over the previous upper bound of \citeassadi2023generalizing.

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. We present new explicit constructions of WPRGs that fool certain classes of standard-order read-once branching programs. In particular, our WPRGs fool width-3 programs, constant-width regular programs, and unbounded-width permutation programs with a single accepting vertex. In all three cases, the seed length is $\widetilde{O}(\log n \cdot \sqrt{\log (1 / \varepsilon)}+\log (1 / \varepsilon))$, where n is the length of the program and $\varepsilon$ is the error of the WPRG. For comparison, for all three of these models, the best explicit unweighted PRGs known have seed length $\widetilde{O}(\log n$. $\log (1 / \varepsilon)$) (Meka, Reingold, and Tal STOC 2019; Braverman, Rao, Raz, and Yehudayoff SICOMP 2014; Hoza, Pyne, and Vadhan ITCS 2021). Our WPRG seed length is superior when $\varepsilon$ is small. For the case of unbounded-width permutation programs, Pyne and Vadhan previously constructed a WPRG with a seed length that is similar to ours (CCC 2021), but their seed length has an extra additive $\log ^{3 / 2} n$ term, so our WPRG is superior when $\varepsilon \gg 1 / n$. Our results are based on a new, general framework for error reduction. Our framework builds on the remarkable recent work by Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020) that gave a near-logarithmic space algorithm for estimating random walk probabilities in Eulerian digraphs with high precision. Our framework centers around the “inverse analysis” of random walks and a key combinatorial structure termed “shortcut graphs.” Using our new framework and the recent notion of singular value approximation (Ahmadinejad, Peebles, Pyne, Sidford, and Vadhan arXiv 2023), we also present an alternative, simpler proof of Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan’s main theorem. Compared to the original proof, our new proof avoids much of the sophisticated machinery that was imported from recent work on fast Laplacian solvers.

In his breakthrough paper, Raz showed that any parity learning algorithm requires either quadratic memory or an exponential number of samples [FOCS’16, JACM’19]. A line of work that followed extended this result to a large class of learning problems. Until recently, all these results considered learning in the streaming model, where each sample is drawn independently, and the learner is allowed a single pass over the stream of samples. Garg, Raz, and Tal [CCC’19] considered a stronger model, allowing multiple passes over the stream. In the 2-pass model, they showed that learning parities of size n requires either a memory of size $n^{1.5}$ or at least $2^{\sqrt{n}}$ samples. (Their result also generalizes to other learning problems.) In this work, for any constant q, we prove tight memory-sample lower bounds for any parity learning algorithm that makes q passes over the stream of samples. We show that such a learner requires either $\Omega\left(n^{2}\right)$ memory size or at least $2^{\Omega(n)}$ samples. Beyond establishing a tight lower bound, this is the first nontrivial lower bound for q-pass learning for any $q \geq 3$. Similar to prior work, our results extend to any learning problem with many nearly-orthogonal concepts.We complement the lower bound with an upper bound, showing that parity learning with q passes can be done efficiently with $O\left(n^{2} / \log q\right)$ memory.

Fast matrix multiplication is one of the most fundamental problems in algorithm research. The exponent of the optimal time complexity of matrix multiplication is usually denoted by $\omega$. This paper discusses new ideas for improving the laser method for fast matrix multiplication. We observe that the analysis of higher powers of the Coppersmith-Winograd tensor [Coppersmith & Winograd 1990] incurs a “combination loss”, and we partially compensate for it using an asymmetric version of CW’s hashing method. By analyzing the eighth power of the CW tensor, we give a new bound of $\omega/\lt2.371866$, which improves the previous best bound of $\omega/\lt2.372860$ [Alman & Vassilevska Williams 2020]. Our result breaks the lower bound of 2.3725 in [Ambainis, Filmus & Le Gall 2015] because of the new method for analyzing component (constituent) tensors.

We consider low-space algorithms for the classic Element Distinctness problem: given an array of n input integers with O(log n) bit-length, decide whether or not all elements are pairwise distinct. Beame, Clifford, and Machmouchi [FOCS 2013] gave an Õ(n1.5)-time randomized algorithm for Element Distinctness using only O(log n) bits of working space. However, their algorithm assumes a random oracle (in particular, read-only random access to polynomially many random bits), and it was asked as an open question whether this assumption can be removed. In this paper, we positively answer this question by giving an Õ(n1.5)-time randomized algorithm using O(log3 n log log n) bits of space, with one-way access to random bits. As a corollary, we also obtain a poly(n)-space O∗(20.86n)-time randomized algorithm for the Subset Sum problem, removing the random oracles required in the algorithm of Bansal, Garg, Nederlof, and Vyas [STOC 2017]. The main technique underlying our results is a pseudorandom hash family based on iterative restrictions, which can fool the cycle-finding procedure in the algorithms of Beame et al. and Bansal et al.

Motivated by display advertising on the internet, the online stochastic matching problem is proposed by Feldman, Mehta, Mirrokni, and Muthukrishnan (FOCS 2009). Consider a stochastic bipartite graph with offline vertices on one side and with i.i.d. online vertices on the other side. The algorithm knows the offline vertices and the distribution of the online vertices in advance. Upon the arrival of each online vertex, its type is realized and the algorithm immediately and irrevocably decides how to match it. In the vertex-weighted version of the problem, each offline vertex is associated with a weight and the goal is to maximize the total weight of the matching.

With a wide range of applications, stochastic matching problems have been studied in different models, including prophet inequality, Query-Commit, and Price-of-Information. While there have been recent breakthroughs in all these settings for bipartite graphs, few non-trivial results are known for general graphs. In this paper, we study the random order vertex arrival contention resolution scheme for matching in general graphs, which is inspired by the recent work of Ezra et al. (EC 2020). We design an 8/15-selectable batched RCRS for matching and apply it to achieve 8/15-competitive/approximate algorithms for all the three models. Our results are the first non-trivial results for random order prophet matching and Price-of-Information matching in general graphs. For the Query-Commit model, our result substantially improves upon the 0.501 approximation ratio by Tang et al. (STOC 2020). We also show that no batched RCRS for matching can be better than 1/2+1/(2e²) ≈ 0.567-selectable.

In biology, phylogenetic trees are important tools for describing evolutionary relations, but various data sources may result in conflicting phylogenetic trees. To summarize these conflicting phylogenetic trees, consensus tree methods take k conflicting phylogenetic trees (each with n leaves) as input and output a single phylogenetic tree as consensus. Among the consensus tree methods, a widely used method is the greedy consensus tree. The previous fastest algorithms for constructing a greedy consensus tree have time complexity Õ(kn^1.5) [Gawrychowski, Landau, Sung, Weimann 2018] and Õ(k²n) [Sung 2019] respectively. In this paper, we improve the running time to Õ(kn). Since k input trees have Θ(kn) nodes in total, our algorithm is optimal up to polylogarithmic factors.

In this paper, we present an improved algorithm for the All Pairs Non-decreasing Paths (APNP) problem on weighted simple digraphs, which has running time $\tilde{O}(n^{\frac{3 + ω}{2}}) = \tilde{O}(n^{2.686})$. Here $n$ is the number of vertices, and $ω< 2.373$ is the exponent of time complexity of fast matrix multiplication [Williams 2012, Le Gall 2014]. This matches the current best upper bound for $(\max, \min)$-matrix product [Duan, Pettie 2009] which is reducible to APNP. Thus, further improvement for APNP will imply a faster algorithm for $(\max, \min)$-matrix product. The previous best upper bound for APNP on weighted digraphs was $\tilde{O}(n^{\frac{1}{2}(3 + \frac{3 - ω}{ω+ 1} + ω)}) = \tilde{O}(n^{2.78})$ [Duan, Gu, Zhang 2018]. We also show an $\tilde{O}(n^2)$ time algorithm for APNP in undirected graphs which also reaches optimal within logarithmic factors.

Given n positive integers, the Modular Subset Sum problem asks if a subset adds up to a given target t modulo a given integer m. This is a natural generalization of the Subset Sum problem (where m = +∞) with ties to additive combinatorics and cryptography. Recently, in [Bri17, KX17], efficient algorithms have been developed for the non-modular case, running in near-linear pseudo-polynomial time. For the modular case, however, the best known algorithm by Koiliaris and Xu [KX17] runs in time Õ(m5/4). In this paper, we present an algorithm running in Õ(m) randomized time, which matches a recent conditional lower bound of [ABHS17] based on the Strong Exponential Time Hypothesis. Interestingly, in contrast to most previous results on Subset Sum, our algorithm does not use the Fast Fourier Transform. Instead, it is able to simulate the “textbook” Dynamic Programming algorithm much faster, using ideas from linear sketching. This is one of the first applications of sketching-based techniques to obtain fast algorithms for exact combinatorial problems in an offline setting.