We develop algorithms for the approximate Orthogonal Vectors (OV) and Diameter problems over the Hamming space. Prior work exhibited an intriguing sharp transition: for approximation factor c=2, the algorithms are simple and run in Õ(nd) time; whereas already for c=2-δ, the best known approach has been to reduce the problems to nearest neighbor search, leading to solutions with runtimes of the form n1+ω(1). Our algorithms solve (2-δ)-approximate OV and Diameter with runtimes of n1+O(δ) and n1+O(√δ), respectively. The improvement also holds for the online (data structure) versions: online OV and Furthest Neighbor Search (FNS). This is the first direct improvement for approximate FNS in the Hamming space since [Goel, Indyk, Varadarajan 2001]. Our approach consists of two key steps. First, we define a "heterogeneous"pseudo-random instance of the problems and prove a structural lemma showing that any such instance is solved by one of three simple algorithms. Second, we develop a specialized regularity lemma that allows one to reduce any arbitrary dataset to such a pseudo-random instance.

In this paper we consider generalized flow problems where there is an m-edge n-node directed graph $G=(V, E)$ and each edge $e \in E$ has a loss factor $\gamma_{e}\gt 0$ governing whether the flow is increased or decreased as it crosses edge e. We provide a randomized $\widetilde{O}\left(\left(m+n^{1.5}\right) \cdot \operatorname{polylog}\left(\frac{W}{\delta}\right)\right)$ time algorithm for solving the generalized maximum flow and generalized minimum cost flow problems in this setting where $\delta$ is the target accuracy and W is the maximum of all costs, capacities, and loss factors and their inverses. This improves upon the previous state-of-the-art $\widetilde{O}\left(m \sqrt{n} \cdot \log ^{2}\left(\frac{W}{\delta}\right)\right)$ time algorithm, obtained by combining the algorithm of [17] with techniques from [29]. To obtain this result we provide new dynamic data structures and spectral results regarding the matrices associated to generalized flows and apply them through the interior point method framework of [39].1.1The full version of this paper is available at https://arxiv.org/abs/2510.17740.

We propose a randomized multiplicative weight update (MWU) algorithm for 𝓁_{∞} regression that runs in Õ(n^{2+1/22.5} poly(1/ε)) time when ω = 2+o(1), improving upon the previous best Õ(n^{2+1/18} polylog(1/ε)) runtime in the low-accuracy regime. Our algorithm combines state-of-the-art inverse maintenance data structures with acceleration. In order to do so, we propose a novel acceleration scheme for MWU that exhibits stability and robustness, which are required for the efficient implementations of the inverse maintenance data structures. We also design a faster deterministic MWU algorithm that runs in Õ(n^{2+1/12}poly(1/ε)) time when ω = 2+o(1), improving upon the previous best Õ(n^{2+1/6} poly log(1/ε)) runtime in the low-accuracy regime. We achieve this by showing a novel stability result that goes beyond previously known works based on interior point methods (IPMs). Our work is the first to use acceleration and inverse maintenance together efficiently, finally making the two most important building blocks of modern structured convex optimization compatible.

We present a general framework for designing efficient data structures for high-dimensional pattern-matching problems ($\exists \;? i\in[n], f(x_i,y)=1$) through communication models in which $f(x,y)$ admits sublinear communication protocols with exponentially-small error. Specifically, we reduce the data structure problem to the Unambiguous Arthur-Merlin (UAM) communication complexity of $f(x,y)$ under product distributions. We apply our framework to the Partial Match problem (a.k.a, matching with wildcards), whose underlying communication problem is sparse set-disjointness. When the database consists of $n$ points in dimension $d$, and the number of $\star$'s in the query is at most $w = c\log n \;(\ll d)$, the fastest known linear-space data structure (Cole, Gottlieb and Lewenstein, STOC'04) had query time $t \approx 2^w = n^c$, which is nontrivial only when $c<1$. By contrast, our framework produces a data structure with query time $n^{1-1/(c \log^2 c)}$ and space close to linear. To achieve this, we develop a one-sided $ε$-error communication protocol for Set-Disjointness under product distributions with $\tildeΘ(\sqrt{d\log(1/ε)})$ complexity, improving on the classical result of Babai, Frankl and Simon (FOCS'86). Building on this protocol, we show that the Unambiguous AM communication complexity of $w$-Sparse Set-Disjointness with $ε$-error under product distributions is $\tilde{O}(\sqrt{w \log(1/ε)})$, independent of the ambient dimension $d$, which is crucial for the Partial Match result. Our framework sheds further light on the power of data-dependent data structures, which is instrumental for reducing to the (much easier) case of product distributions.

We prove direct-sum theorems for Wilber's two lower bounds [Wilber, FOCS'86] on the cost of access sequences in the binary search tree (BST) model. These bounds are central to the question of dynamic optimality [Sleator and Tarjan, JACM'85]: the Alternation bound is the only bound to have yielded online BST algorithms beating $\log n$ competitive ratio, while the Funnel bound has repeatedly been conjectured to exactly characterize the cost of executing an access sequence using the optimal tree [Wilber, FOCS'86, Kozma'16], and has been explicitly linked to splay trees [Levy and Tarjan, SODA'19]. Previously, the direct-sum theorem for the Alternation bound was known only when approximation was allowed [Chalermsook, Chuzhoy and Saranurak, APPROX'20, ToC'24]. We use these direct-sum theorems to amplify the sequences from [Lecomte and Weinstein, ESA'20] that separate between Wilber's Alternation and Funnel bounds, increasing the Alternation and Funnel bounds while optimally maintaining the separation. As a corollary, we show that Tango trees [Demaine et al., FOCS'04] are optimal among any BST algorithms that charge their costs to the Alternation bound. This is true for any value of the Alternation bound, even values for which Tango trees achieve a competitive ratio of $o(\log \log n)$ instead of the default $O(\log \log n)$. Previously, the optimality of Tango trees was shown only for a limited range of Alternation bound [Lecomte and Weinstein, ESA'20].

We settle the complexity of dynamic least-squares regression (LSR), where rows and labels $\left(\mathbf{A}^{(t)}, \mathbf{b}^{(t)}\right)$ can be adaptively inserted and/or deleted, and the goal is to efficiently maintain an $\epsilon$-approximate solution to $\min _{\mathbf{x}^{(t)}}\left\|\mathbf{A}^{(t)} \mathbf{x}^{(t)}-\mathbf{b}^{(t)}\right\|_{2}$ for all $t \in[T]$. We prove sharp separations $\left(d^{2-o(1)}\right.$ vs. $\left.\sim d\right)$ between the amortized update time of: (i) Fully vs. Partially dynamic 0.01-LSR; (ii) High vs. low-accuracy LSR in the partially-dynamic (insertion-only) setting.Our lower bounds follow from a gap-amplification reduction–reminiscent of iterative refinement-from the exact version of the Online Matrix Vector Conjecture (OMv) [HKNS15], to constant approximate OMv over the reals, where the i-th online product $\mathrm{Hv}^{(i)}$ only needs to be computed to 0.1 -relative error. All previous fine-grained reductions from OMv to its approximate versions only show hardness for inverse polynomial approximation $\epsilon=$ $n^{-\omega(1)}$ (additive or multiplicative). This result is of independent interest in fine-grained complexity and for the investigation of the OMv Conjecture, which is still widely open.

We consider the energy complexity of the leader election problem in the single-hop radio network model, where each device v has a unique identifier ID ( v ) ∈{ 1, 2, ⋖ , N } . Energy is a scarce resource for small battery-powered devices. For such devices, most of the energy is often spent on communication, not on computation. To approximate the actual energy cost, the energy complexity of an algorithm is defined as the maximum over all devices of the number of time slots where the device transmits or listens. Much progress has been made in understanding the energy complexity of leader election in radio networks, but very little is known about the tradeoff between time and energy. Chang et al. [STOC 2017] showed that the optimal deterministic energy complexity of leader election is Θ (log log N ) if each device can simultaneously transmit and listen but still leaving the problem of determining the optimal time complexity under any given energy constraint. Time–energy tradeoff: For any k ≥ log log N , we show that a leader among at most n devices can be elected deterministically in O ( k ċ n 1+ε ) + O ( k ċ N 1/k ) time and O ( k ) energy if each device can simultaneously transmit and listen, where ε > 0 is any small constant. This improves upon the previous O ( N )-time O (log log N )-energy algorithm by Chang et al. [STOC 2017]. We provide lower bounds to show that the time–energy tradeoff of our algorithm is near-optimal. Dense instances: For the dense instances where the number of devices is n = Θ ( N ), we design a deterministic leader election algorithm using only O (1) energy. This improves upon the O (log* N )-energy algorithm by Jurdziński, Kutyłowski, and Zatopiański [PODC 2002] and the O (α ( N ))-energy algorithm by Chang et al. [STOC 2017]. More specifically, we show that the optimal deterministic energy complexity of leader election is \(\Theta (\max \lbrace 1, \log \tfrac{N}{n}\rbrace)\) if each device cannot simultaneously transmit and listen, and it is \(Θ (\max \lbrace 1, \log \log \tfrac{N}{n}\rbrace)\) if each device can simultaneously transmit and listen.

Many deep learning tasks need to deal with graph data (e.g., social networks, protein structures, code ASTs). Due to the importance of these tasks, people turned to Graph Neural Networks (GNNs) as the de facto method for machine learning on graph data. GNNs have become widely applied due to their convincing performance. Unfortunately, one major barrier to using GNNs is that GNNs require substantial time and resources to train. Recently, a new method for learning on graph data is Graph Neural Tangent Kernel (GNTK). GNTK is an application of Neural Tangent Kernel (NTK) (a kernel method) on graph data, and solving NTK regression is equivalent to using gradient descent to train an infinite-wide neural network. The key benefit of using GNTK is that, similar to any kernel method, GNTK's parameters can be solved directly in a single step, avoiding time-consuming gradient descent. Meanwhile, sketching has become increasingly used in speeding up various optimization problems, including solving kernel regression. Given a kernel matrix of n graphs, using sketching in solving kernel regression can reduce the running time to o(n^3). But unfortunately such methods usually require extensive knowledge about the kernel matrix beforehand, while in the case of GNTK we find that the construction of the kernel matrix is already O(n^2N^4), assuming each graph has N nodes. The kernel matrix construction time can be a major performance bottleneck when the size of graphs N increases. A natural question to ask is thus whether we can speed up the kernel matrix construction to improve GNTK regression's end-to-end running time. This paper provides the first algorithm to construct the kernel matrix in o(n^2N^3) running time.

This paper introduces a new robust interior point method analysis for semidefinite programming (SDP). This new robust analysis can be combined with either logarithmic barrier or hybrid barrier.Under this new framework, we can improve the running time of semidefinite programming (SDP) with variable size $n\times n$ and m constraints up to $\epsilon$ accuracy.We show that for the case $m=\Omega(n^{2})$, we can solve SDPs in $m^{\omega}$ time. This suggests solving SDP is nearly as fast as solving the linear system with equal number of variables and constraints. This is the first result that tall dense SDP can be solved in the nearly-optimal running time, and it also improves the stateof-the-art SDP solver [Jiang, Kathuria, Lee, Padmanabhan and Song, FOCS 2020].In addition to our new IPM analysis, we also propose a number of techniques that might be of further interest, such as, maintaining the inverse of a Kronecker product using lazy updates, a general amortization scheme for positive semi-definite matrices.

We present a faster interior-point method for optimizing sum-of-squares (SOS) polynomials, which are a central tool in polynomial optimization and capture convex programming in the Lasserre hierarchy. Let p = ∑_i q²_i be an n-variate SOS polynomial of degree 2d. Denoting by L : = binom(n+d,d) and U : = binom(n+2d,2d) the dimensions of the vector spaces in which q_i’s and p live respectively, our algorithm runs in time Õ(LU^{1.87}). This is polynomially faster than state-of-art SOS and semidefinite programming solvers [Jiang et al., 2020; Huang et al., 2021; Papp and Yildiz, 2019], which achieve runtime Õ(L^{0.5} min{U^{2.37}, L^{4.24}}). The centerpiece of our algorithm is a dynamic data structure for maintaining the inverse of the Hessian of the SOS barrier function under the polynomial interpolant basis [Papp and Yildiz, 2019], which efficiently extends to multivariate SOS optimization, and requires maintaining spectral approximations to low-rank perturbations of elementwise (Hadamard) products. This is the main challenge and departure from recent IPM breakthroughs using inverse-maintenance, where low-rank updates to the slack matrix readily imply the same for the Hessian matrix.

We consider the time (number of communication rounds) and energy (number of non-idle communication rounds per device) complexities of randomized leader election in a multiple-access channel, where the number of devices n ≥ 2 is unknown. It is well-known that for polynomial-time randomized leader election algorithms with success probability 1 - 1/poly(n), the optimal energy complexity is Θ(log log* n) if receivers can detect collisions, and it is Θ(log* n) otherwise.

Abstract. This paper considers Bayesian revenue maximization in the [Formula: see text]-unit setting, where a monopolist seller has [Formula: see text] copies of an indivisible item and faces [Formula: see text] unit-demand buyers (whose value distributions can be nonidentical). Four basic mechanisms among others have been widely employed in practice and widely studied in the literature: Myerson auction, sequential posted-pricing, [Formula: see text]-th price auction with anonymous reserve, and anonymous pricing. Regarding a pair of mechanisms, we investigate the largest possible ratio between the two revenues (also known as the revenue gap), over all possible value distributions of the buyers. Divide these four mechanisms into two groups: (i) the discriminating mechanism group, Myerson auction and sequential posted-pricing, and (ii) the anonymous mechanism group, anonymous reserve and anonymous pricing. Within one group, the involved two mechanisms have an asymptotically tight revenue gap of [Formula: see text]. In contrast, any two mechanisms from the different groups have an asymptotically tight revenue gap of [Formula: see text].

This paper considers Bayesian revenue maximization in the k-unit setting, where a monopolist seller has k copies of an indivisible item and faces n unit-demand buyers (whose value distributions can be non-identical). Four basic mechanisms among others have been widely employed in practice and widely studied in the literature: Myerson Auction, Sequential Posted-Pricing, (k + 1)-th Price Auction with Anonymous Reserve, and Anonymous Pricing. Regarding a pair of mechanisms, we investigate the largest possible ratio between the two revenues (a.k.a. the revenue gap), over all possible value distributions of the buyers. Divide these four mechanisms into two groups: (i) the discriminating mechanism group, Myerson Auction and Sequential Posted-Pricing, and (ii) the anonymous mechanism group, Anonymous Reserve and Anonymous Pricing. Within one group, the involved two mechanisms have an asymptotically tight revenue gap of 1 + Θ(1 / √k). In contrast, any two mechanisms from the different groups have an asymptotically tight revenue gap of Θ(łog k).

We consider the energy complexity of the leader election problem in the single-hop radio network model, where each device ν has a unique identifier ID(ν) ∈ {1, 2, ..., N}. Energy is a scarce resource for small battery-powered devices. For such devices, most of the energy is often spent on communication, not on computation. To approximate the actual energy cost, the energy complexity of an algorithm is defined as the maximum over all devices of the number of time slots where the device transmits or listens.

The fastest known LP solver for general (dense) linear programs is due to [Cohen, Lee and Song’19] and runs in O*(nω +n2.5−α/2 + n2+1/6) time. A number of follow-up works [Lee, Song and Zhang’19, Brand’20, Song and Yu’20] obtain the same complexity through different techniques, but none of them can go below n2+1/6, even if ω=2. This leaves a polynomial gap between the cost of solving linear systems (nω) and the cost of solving linear programs, and as such, improving the n2+1/6 term is crucial toward establishing an equivalence between these two fundamental problems. In this paper, we reduce the running time to O*(nω +n2.5−α/2 + n2+1/18) where ω and α are the fast matrix multiplication exponent and its dual. Hence, under the common belief that ω ≈ 2 and α ≈ 1, our LP solver runs in O*(n2.055) time instead of O*(n2.16).

A priority queue is a fundamental data structure that maintains a dynamic set of (key, priority)-pairs and supports Insert, Delete, ExtractMin and DecreaseKey operations. In the external memory model, the current best priority queue supports each operation in amortized I/Os. If the DecreaseKey operation does not need to be supported, one can design a more efficient data structure that supports the Insert, Delete and ExtractMin operations in I/Os. A recent result shows that a degradation in performance is inevitable by proving a lower bound of I/Os for priority queues with DecreaseKeys. In this paper we tighten the gap between the lower bound and the upper bound by proposing a new priority queue which supports the DecreaseKey operation and has an expected amortized I/O complexity of . Our result improves the external memory priority queue with DecreaseKeys for the first time in over a decade, and also gives the fastest external memory single source shortest path algorithm.

Training deep neural networks is a highly nontrivial task, involving carefully selecting appropriate training algorithms, scheduling step sizes and tuning other hyperparameters. Trying different combinations can be quite labor-intensive and time consuming. Recently, researchers have tried to use deep learning algorithms to exploit the landscape of the loss function of the training problem of interest, and learn how to optimize over it in an automatic way. In this paper, we propose a new learning-to-learn model and some useful and practical tricks. Our optimizer outperforms generic, hand-crafted optimization algorithms and state-of-the-art learning-to-learn optimizers by DeepMind in many tasks. We demonstrate the effectiveness of our algorithms on a number of tasks, including deep MLPs, CNNs, and simple LSTMs.