Hongxun Wu

SODA Conference 2025 Conference Paper

Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors

• Elena Gribelyuk
• Pachara Sawettamalya
• Hongxun Wu
• Huacheng Yu

FOCS Conference 2025 Conference Paper

Theoretical limitations of multi-layer Transformer

• Lijie Chen 0001
• Binghui Peng
• Hongxun Wu

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.

SODA Conference 2024 Conference Paper

Breaking the Metric Voting Distortion Barrier

• Moses Charikar
• Kangning Wang 0001
• Prasanna Ramakrishnan
• Hongxun Wu

FOCS Conference 2024 Conference Paper

Optimal Quantile Estimation: Beyond the Comparison Model

• Meghal Gupta
• Mihir Singhal
• Hongxun Wu

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.

SODA Conference 2024 Conference Paper

The Cost of Parallelizing Boosting

• Xin Lyu 0002
• Hongxun Wu
• Junzhao Yang

FOCS Conference 2023 Conference Paper

Faster Matrix Multiplication via Asymmetric Hashing

• Ran Duan
• Hongxun Wu
• Renfei Zhou

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.

FOCS Conference 2023 Conference Paper

Tight Time-Space Lower Bounds for Constant-Pass Learning

• Xin Lyu 0002
• Avishay Tal
• Hongxun Wu
• Junzhao Yang

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.

FOCS Conference 2023 Conference Paper

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting

• Lijie Chen 0001
• William M. Hoza
• Xin Lyu 0002
• Avishay Tal
• Hongxun Wu

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.

STOC Conference 2022 Conference Paper

(Fractional) online stochastic matching via fine-grained offline statistics

• Zhihao Gavin Tang
• Jinzhao Wu
• Hongxun Wu

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. In this paper, we generalize the model to allow non-identical online vertices and focus on the fractional version of the vertex-weighted stochastic matching. We design fractional algorithms that are 0.718-competitive and 0.731-competitive for non i.i.d. arrivals and i.i.d. arrivals respectively. We also prove that no fractional algorithm can achieve a competitive ratio better than 0.75 for non i.i.d. arrivals. Furthermore, we round our fractional algorithms by applying the recently developed multiway online correlated selection by Gao et al. (FOCS 2021) and achieve 0.666-competitive and 0.704-competitive integral algorithms for non i.i.d. arrivals and i.i.d. arrivals. Our results for non i.i.d. arrivals are the first algorithms beating the 1−1/ e ≈ 0.632 barrier of the classical adversarial setting. Our 0.704-competitive integral algorithm for i.i.d. arrivals slightly improves the state-of-the-art 0.701-competitive ratio by Huang and Shu (STOC 2021).

SODA Conference 2022 Conference Paper

Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions

• Lijie Chen 0001
• Ce Jin 0001
• R. Ryan Williams
• Hongxun Wu

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 Õ ( n 1. 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 Õ ( n 1. 5 )-time randomized algorithm using O (log 3 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 ∗ (2 0. 86 n )-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.

SODA Conference 2019 Conference Paper

Fast Modular Subset Sum using Linear Sketching

• Kyriakos Axiotis
• Arturs Backurs
• Ce Jin 0001
• Christos Tzamos
• Hongxun Wu

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 Õ ( m 5/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.