We prove that for any 3-player game G, whose query distribution has the same support as the GHZ game (i.e., all x,y,z ∈ {0,1} satisfying x+y+z = 0 (mod 2)), the value of the n-fold parallel repetition of G decays exponentially fast: val(G^{⊗ n}) ≤ exp(-n^c) for all sufficiently large n, where c > 0 is an absolute constant. We also prove a concentration bound for the parallel repetition of the GHZ game: For any constant ε > 0, the probability that the players win at least a (3/4+ε) fraction of the n coordinates is at most exp(-n^c), where c = c(ε) > 0 is a constant. In both settings, our work exponentially improves upon the previous best known bounds which were only polynomially small, i.e., of the order n^{-Ω(1)}. Our key technical tool is the notion of algebraic spreadness adapted from the breakthrough work of Kelley and Meka (FOCS '23) on sets free of 3-term progressions.

We identify a sharp separation in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut (rather than only the approximate value). For dense graphs, we show that O(n/ε²) space is sufficient and that Ω(n) space is necessary. In contrast, for graphs with Θ(n/ε²) edges, the situation is markedly different: we show that the problem requires Ω(n log(ε² n)/ε²) space for any ε = ω(1/√n), which is tight for the full range of ε. We also give an Ω(n log n/ε²)-space lower bound against deterministic algorithms for outputting a (1-ε) approximation to the value of the maximum cut. Using similar techniques we prove an analogous sharp separation in the streaming space complexity of Densest Subgraph and show that for every constant-arity CSP over a constant-size alphabet and the Similarity problem the space complexity in dense streams can be improved by shaving a logarithmic factor.

In this paper, we revisit spectral sparsification for sums of arbitrary positive semidefinite (PSD) matrices. Concretely, for any collection of PSD matrices \(\mathcal{A}=\{A_1,A_2,\ldots,A_r\}\subseteq \mathbb{R}^{n\times n}\), given any subset \(T\subseteq [r]\), our goal is to find sparse weights \(\mu_i\in\mathbb{R}_{\ge 0}\) such that \((1-\varepsilon)\sum_{i\in T} A_i \;\preceq\; \sum_{i\in T} \mu_i A_i \;\preceq\; (1+\varepsilon)\sum_{i\in T} A_i\). This generalizes spectral sparsification of graphs which corresponds to \(\mathcal{A}\) being the set of Laplacians of edges. It also captures sparsifying Cayley graphs by choosing a subset of generators. The former has been extensively studied with optimal sparsifiers known. The latter has received attention recently and was solved for a few special groups (e.g., \(\mathbb{F}_2^n\)). Prior work shows any sum of PSD matrices can be sparsified down to \(O(n)\) elements. This bound however turns out to be too coarse and in particular yields no non-trivial bound for building Cayley sparsifiers for Cayley graphs. In this work, we develop a new, instance-specific (i.e., specific to a given collection \(\mathcal{A}\)) theory of PSD matrix sparsification based on a new parameter \(N^*(\mathcal{A})\) which we call connectivity threshold that generalizes the threshold of the number of edges required to make a graph connected. Our main result gives a sparsifier that uses at most \(O(\varepsilon^{-2} N^*(\mathcal{A}) (\log n) (\log r))\) matrices and is constructible in randomized polynomial time. We also show that we need \(N^*(\mathcal{A})\) elements to sparsify for any \(\varepsilon \lt 0.99\). As the main application of our framework, we prove that any Cayley graph can be sparsified to \(O(\varepsilon^{-2}\log^4 N)\) generators. Previously, a non-trivial bound on Cayley sparsifiers was known only in the case when the group is \(\mathbb{F}_2^n\).

We give an algorithm that takes a directed graph $G$ undergoing $m$ edge insertions with lengths in $[1, W]$, and maintains $(1+ε)$-approximate shortest path distances from a fixed source $s$ to all other vertices. The algorithm is deterministic and runs in total time $m^{1+o(1)}\log W$, for any $ε> \exp(-(\log m)^{0.99})$. This is achieved by designing a nonstandard interior point method to crudely detect when the distances from $s$ other vertices $v$ have decreased by a $(1+ε)$ factor, and implementing it using the deterministic min-ratio cycle data structure of [Chen-Kyng-Liu-Meierhans-Probst, STOC 2024].

The problem of studying k-wise correlations in product spaces, i.e., correlations of the form ${\mathbb{E}_{\left( {{x_1}, \ldots ,{x_k}} \right)\sim \mu \otimes n}}\left[ {{f_1}\left( {{x_1}} \right) \cdots f\left( {{x_k}} \right)} \right]$ where ${\text{ }}{f_i}:\sum\nolimits_i^n \to \mathbb{C}$ are all 1-bounded functions and µ is a distribution over Σ1× … × Σk, appears in many different contexts throughout discrete mathematics. Examples include additive combinatorics, extremal combinatorics, hardness of approximation and probability. The goal in an inverse theorem is to characterize the type of functions f1,…,fkthat achieve non-trivial correlations, under minimal assumptions on the distribution µ.We give new inverse theorems for k-wise correlations for all k ⩾ 3. For k = 3, our inverse theorem works for any distribution µ which is pairwise-connected, which is essentially the minimal assumption required for a nontrivial inverse theorem to hold. For k > 3, our inverse theorem applies for distributions µ satisfying the stronger condition of not having any Abelian embeddings. This resolves a conjecture from [Bhangale-Khot-Minzer, STOC 2022].We give applications of our inverse theorems to additive combinatorics, hardness of approximation, and property testing. First, we show that there exists c > 0 such that any set A ⊆ {0,1,2}nwith density at least Ω((loglogloglogn)−c) must contain a combinatorial line, i.e., x,y,z ∈ {0,1,2}n, not all equal, such that xi= yi= zior (xi,yi,zi) = (0,1,2) for all i = 1,2,…,n. In other words, we give "reasonable bounds" for the density Hales-Jewett theorem of length 3. This involves combining our inverse theorems with several additional insights, motivated by Shkredov’s proof of the corners theorem and Polymath’s combinatorial proof of the density Hales-Jewett theorem. Second, we show how to construct a dictatorship vs quasi-random test that has perfect completeness and soundness s + ε from integrality gap instances with similar parameters, provided that its local distributions have no Abelian embeddings. Third, we analyze the direct-sum tester of [Dinur-Golubev, RANDOM 2019] in the low-soundness regime.

Let G be a finite abelian group and A be a subset of $G \times G$ which is corner-free, meaning that there are no $x, y \in G$ and $d \in G \backslash\{0\}$ such that $(x, y),(x+d, y),(x, y+d) \in A$. We prove that \begin{equation*}|A| \leq|G|^{2} \cdot \exp \left(-(\log |G|)^{\Omega{1}}\right)\end{equation*}As a consequence, we obtain polynomial (in the input length) lower bounds on the non-deterministic communication complexity of Exactly-N in the 3-player Number-on-Forehead model. We also obtain the first “reasonable” lower bounds on the coloring version of the 3 -dimensional corners problem, as well as on the non-deterministic communication complexity of Exactly-N in the 4-player Number-on-Forehead model. This is an extended abstract. The full version of the paper can be found at https://arxiv.org/abs/2504.07006.

We present an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in \(m^{1+o(1)}\) time. Our algorithm builds the flow through a sequence of \(m^{1+o(1)}\) approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized \(m^{o(1)}\) time using a new dynamic graph data structure. Our framework extends to algorithms running in \(m^{1+o(1)}\) time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p -norm flows, and p -norm isotonic regression on arbitrary directed acyclic graphs.

Abstract. We design fast algorithms for repeatedly sampling from strongly Rayleigh distributions, which include as special cases random spanning tree distributions and determinantal point processes. For a graph [Formula: see text], we show how to approximately sample uniformly random spanning trees from [Formula: see text] in [Formula: see text] (Throughout, [Formula: see text] hides polylogarithmic factors in [Formula: see text].) time per sample after an initial [Formula: see text] time preprocessing. This is the first nearly linear runtime in the output size, which is clearly optimal. For a determinantal point process on [Formula: see text]-sized subsets of a ground set of [Formula: see text] elements, defined via an [Formula: see text] kernel matrix, we show how to approximately sample in [Formula: see text] time after an initial [Formula: see text] time preprocessing, where [Formula: see text] is the matrix multiplication exponent. The time to compute just the weight of the output set is simply [Formula: see text], a natural barrier that suggests our runtime might be optimal for determinantal point processes as well. As a corollary, we even improve the state of the art for obtaining a single sample from a determinantal point process, from the prior runtime of [Formula: see text] to [Formula: see text]. In our main technical result, we achieve the optimal limit on domain sparsification for strongly Rayleigh distributions. In domain sparsification, sampling from a distribution [Formula: see text] on [Formula: see text] is reduced to sampling from related distributions on [Formula: see text] for [Formula: see text]. We show that for strongly Rayleigh distributions, the domain size can be reduced to nearly linear in the output size [Formula: see text], improving the state of the art from [Formula: see text] for general strongly Rayleigh distributions and the more specialized [Formula: see text] for spanning tree distributions. Our reduction involves sampling from [Formula: see text] domain-sparsified distributions, all of which can be produced efficiently assuming approximate overestimates for marginals of [Formula: see text] are known and stored in a convenient data structure. Having access to marginals is the discrete analogue of having access to the mean and covariance of a continuous distribution, or equivalently knowing “isotropy” for the distribution, the key behind optimal samplers in the continuous setting based on the famous Kannan–Lovász–Simonovits (KLS) conjecture. We view our result as analogous in spirit to the KLS conjecture and its consequences for sampling, but rather for discrete strongly Rayleigh measures.

We give the first almost-linear total time algorithm for deciding if a flow of cost at most$F$still exists in a directed graph, with edge costs and capacities, undergoing decremental updates, i.e., edge deletions, capacity decreases, and cost increases. This implies almost-linear time algorithms for approximating the minimum-cost flow value and s-t distance on such decremental graphs. Our framework additionally allows us to maintain decremental strongly connected components in almost-linear time deterministically. These algorithms also improve over the current best known runtimes for statically computing minimum-cost flow, in both the randomized and deterministic settings. We obtain our algorithms by taking the dual perspective, which yields cut-based algorithms. More precisely, our algorithm computes the flow via a sequence of$m^{1+o(1)}$-dynamic min-ratio cut problems, the dual analog of the dynamic min-ratio cycle problem that underlies recent fast algorithms for minimum-cost flow. Our main technical contribution is a new data structure that returns an approximately optimal min-ratio cut in amortized$m^{o(1)}$time by maintaining a tree-cut sparsifier. This is achieved by devising a new algorithm to maintain the dynamic expander hierarchy of [$\text{Goranci-Racke-}$SaranurakTan, SODA 2021] that also works in capacitated graphs. All our algorithms are deterministc, though they can be sped up further using randomized techniques while still working against an adaptive adversary.

We study connections between the problem of fully dynamic$(1-\epsilon)$-approximate maximum bipartite matching, and the dual$(1+\epsilon)$-approximate vertex cover problem, with the online matrix-vector (OMv) conjecture which has recently been used in several fine-grained hardness reductions. We prove that there is an online algorithm that maintains a$(1+\epsilon)$-approximate vertex cover in amortized$n^{1-c}\epsilon^{-C}$time for constants$c, C > 0$for fully dynamic updates if and only if the OMv conjecture is false. Similarly, we prove that there is an online algorithm that maintains a$(1-\epsilon)$-approximate maximum matching in amortized$n^{1-c}\epsilon^{-C}$time if and only if there is a nontrivial algorithm for another dynamic problem, which we call dynamic approximate OMv, that has seemingly no matching structure. This provides some evidence against achieving amortized sublinear update times for approximate fully dynamic matching and vertex cover. Leveraging these connections, we obtain faster algorithms for approximate fully dynamic matching in both the online and offline settings. We give a randomized algorithm that with high probability maintains a$(1-\epsilon)$-approximate bipartite matching and$(1+\epsilon)$-approximate vertex cover in fully dynamic graphs, in amortized$O(\epsilon^{-O(1)}\frac{n}{2^{\Omega}(\sqrt{\log n})})$up-date time. This improves over the previous fastest runtimes of$O(n/(\log^{*}n)^{\Omega(1)})$due to Assadi-Behnezhad-Khanna-Li [STOC 2023], and$O_{\epsilon}(n^{1-\Omega_{\epsilon}(1)})$due to Bhattacharya-Kiss-Saranurak [FOCS 2023] for small$\epsilon$. Our algorithm leverages fast algorithms for OMv due to Larsen and Williams [SODA 2017]. We give a randomized offline algorithm for (1 -$\epsilon)$-approximate maximum matching with amortized runtime$O(n^{.58}\epsilon^{-O(1)})$by using fast matrix multi-plication, significantly improving over the runtimes achieved via online algorithms mentioned above. This mirrors the situation with OMv, where an offline algorithm exactly corresponds to fast matrix mul-tiplication. We also give an offline algorithm that maintains a$(1+\epsilon)$-approximate vertex cover in amortized$O(n^{.723}\epsilon^{-O(1)})$time.

We provide an algorithm which, with high probability, maintains a (1 — ɛ)-approximate maximum flow on an undirected graph undergoing m-edge additions in amortized mo(1)ɛ-3 time per update. To obtain this result, we provide a more general algorithm that solves what we call the incremental, thresholded, p-norm flow problem that asks to determine the first edge-insertion in an undirected graph that causes the minimum ℓp-norm flow to decrease below a given threshold in value. Since we solve this thresholded problem, our data structure succeeds against an adaptive adversary that can only see the data structure's output. Furthermore, since our algorithm holds for p = 2, we obtain improved algorithms for dynamically maintaining the effective resistance between a pair of vertices in an undirected graph undergoing edge insertions.

We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, s-t shortest path, maximum flow, and minimum-cost flow. To solve these problems, we give a deterministic data structure that returns a mo(1)-approximate minimum-ratio cycle in fully dynamic graphs in amortized mo(1) time per update. Combining this with the interior point method framework of Brand-Liu-Sidford (STOC 2023) gives the first almost-linear time algorithm for deciding the first update in an incremental graph after which the cost of the minimum-cost flow attains value at most some given threshold F. By rather direct reductions to minimum-cost flow, we are then able to solve the problems in incremental graphs mentioned above.

We consider the sparsification of sums F : ℝn → ℝ+ where F(x) = f1(⟨ a1,x⟩) + ⋯ + fm(⟨ am,x⟩) for vectors a1,…,am ∈ ℝn and functions f1,…,fm : ℝ → ℝ+. We show that (1+ε)-approximate sparsifiers of F with support size n/ε2 (logn/ε)O(1) exist whenever the functions f1,…,fm are symmetric, monotone, and satisfy natural growth bounds. Additionally, we give efficient algorithms to compute such a sparsifier assuming each fi can be evaluated efficiently. Our results generalize the classical case of ℓp sparsification, where fi(z) = |z|p, for p ∈ (0, 2], and give the first near-linear size sparsifiers in the well-studied setting of the Huber loss function and its generalizations, e.g., fi(z) = min{|z|p, |z|2} for 0 < p ≤ 2. Our sparsification algorithm can be applied to give near-optimal reductions for optimizing a variety of generalized linear models including ℓp regression for p ∈ (1, 2] to high accuracy, via solving (logn)O(1) sparse regression instances with m ≤ n(logn)O(1), plus runtime proportional to the number of nonzero entries in the vectors a1, …, am.

We present an algorithm which given any $m$-edge directed graph with positive integer capacities at most $U$, vertices $a$ and $b$, and an approximation parameter $\epsilon \in (0, 1)$ computes an additive $\epsilon mU$-approximate $a$-$b$ maximum flow in time $m^{1+o(1)}/\sqrt{\epsilon}$. By applying the algorithm for $\epsilon = (mU)^{-2/3}$, rounding to an integral flow, and using augmenting paths, we obtain an algorithm which computes an exact $a$-$b$ maximum flow in time $m^{4/3+o(1)}U^{1/3}$ and an algorithm which given an $m$-edge bipartite graph computes an exact maximum cardinality matching in time $m^{4/3+o(1)}$.

Abstract. We give an online algorithm that with high probability computes a [Formula: see text] edge coloring on a graph [Formula: see text] with maximum degree [Formula: see text] under online edge arrivals against oblivious adversaries, making first progress on the conjecture of Bar-Noy, Motwani, and Naor in this general setting. Our algorithm is based on reducing to a matching problem on locally treelike graphs, and then applying a tree recurrence based approach for arguing correlation decay.

We give a deterministic $m^{1+o(1)}$ time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities. As a consequence, we obtain the first running time improvement for deterministic algorithms that compute maximum-flow in graphs with polynomial bounded capacities since the work of Goldberg-Rao [J.ACM ’98].Our algorithm builds on the framework of Chen-Kyng-Liu-Peng-Gutenberg-Sachdeva [FOCS ’22] that computes an optimal flow by computing a sequence of $m^{1+o(1)}$-approximate undirected minimum-ratio cycles. We develop a deterministic dynamic graph data-structure to compute such a sequence of minimum-ratio cycles in an amortized $m^{o(1)}$ time per edge update. Our key technical contributions are deterministic analogues of the vertex sparsification and edge sparsification components of the data-structure from Chen et al. For the vertex sparsification component, we give a method to avoid the randomness in Chen et al. which involved sampling random trees to recurse on. For the edge sparsification component, we design a deterministic algorithm that maintains an embedding of a dynamic graph into a sparse spanner. We also show how our dynamic spanner can be applied to give a deterministic data structure that maintains a fully dynamic low-stretch spanning tree on graphs with polynomially bounded edge lengths, with subpolynomial average stretch and subpolynomial amortized time per edge update.

Abstract-For any norms $N_{1}, \ldots, N_{m}$ on $\mathbb{R}^{n}$ and $N(x):= N_{1}(x)+\cdots+N_{m}(x)$, we show there is a sparsified norm $\tilde{N}(x)= w_{1} N_{1}(x)+\cdots+w_{m} N_{m}(x)$ such that $|N(x)-\tilde{N}(x)| \leqslant \varepsilon N(x)$ for all $x \in \mathbb{R}^{n}$, where $w_{1}, \ldots, w_{m}$ are non-negative weights, of which only $O\left(\varepsilon^{-2} n \log (n / \varepsilon)(\log n)^{2.5}\right)$ are non-zero. Additionally, we show that such weights can be found with high probability in time $O\left(m(\log n)^{O(1)}+\right.$ poly $\left.(n)\right) T$, where T is the time required to evaluate a norm $N_{i}(x)$, assuming that $N(x)$ is poly $(n)$ equivalent to the Euclidean norm. This immediately yields analogous statements for sparsifying sums of symmetric submodular functions. More generally, we show how to sparsify sums of p th powers of norms when the sum is p-uniformly smooth.1

In this paper we provide an algorithm for maintaining a (1−є)-approximate maximum flow in a dynamic, capacitated graph undergoing edge insertions. Over a sequence of m insertions to an n-node graph where every edge has capacity O(poly(m)) our algorithm runs in time O(m √n · є−1). To obtain this result we design dynamic data structures for the more general problem of detecting when the value of the minimum cost circulation in a dynamic graph undergoing edge insertions achieves value at most F (exactly) for a given threshold F. Over a sequence m insertions to an n-node graph where every edge has capacity O(poly(m)) and cost O(poly(m)) we solve this thresholded minimum cost flow problem in O(m √n). Both of our algorithms succeed with high probability against an adaptive adversary. We obtain these results by dynamizing the recent interior point method by [Chen et al. ‍FOCS 2022] used to obtain an almost linear time algorithm for minimum cost flow, and introducing a new dynamic data structure for maintaining minimum ratio cycles in an undirected graph that succeeds with high probability against adaptive adversaries.

We present an algorithm that given any n-vertex, m-edge, rank r hypergraph constructs a spectral sparsifier with O(n ε−2 logn logr) hyperedges in nearly-linear O(mr) time. This improves in both size and efficiency over a line of work [Bansal-Svensson-Trevisan 2019, Kapralov-Krauthgamer-Tardos-Yoshida 2021] for which the previous best size was O(min{n ε−4 log3 n,nr3 ε−2 logn}) and runtime was O(mr + nO(1)).

We design fast algorithms for repeatedly sampling from strongly Rayleigh distributions, which include as special cases random spanning tree distributions and determinantal point processes. For a graph $G=(V,\ E)$, we show how to approximately sample uniformly random spanning trees from G in $O(|V|)$1time per sample after an initial $O(|E|)$ time preprocessing. This is the first nearly-linear runtime in the output size, which is clearly optimal. For a determinantal point process on k-sized subsets of a ground set of n elements, defined via an $n\times n$ kernel matrix, we show how to approximately sample in ${\widetilde{O}}(k^{\omega})$ time after an initial ${\widetilde{O}}(nk^{\omega-1})$ time preprocessing, where $\omega\lt 2.372864$ is the matrix multiplication exponent. The time to compute just the weight of the output set is simply $\simeq k^{\omega}$, a natural barrier that suggests our runtime might be optimal for determinantal point processes as well. As a corollary, we even improve the state of the art for obtaining a single sample from a determinantal point process, from the prior runtime of ${\widetilde{O}}(\min\{nk^{2},\ n^{\omega}\})$ to ${\widetilde{O}}(nk^{\omega-1})$.In our main technical result, we achieve the optimal limit on domain sparsification for strongly Rayleigh distributions. In domain sparsification, sampling from a distribution $\mu$ on $\binom{[n]}{k}$ is reduced to sampling from related distributions on $\binom{[t]}{k}$ for $t\ll n$. We show that for strongly Rayleigh distributions, the domain size can be reduced to nearly linear in the output size $t={\widetilde{O}}(k)$, improving the state of the art from $t={\widetilde{O}}(k^{2})$ for general strongly Rayleigh distributions and the more specialized $t={\widetilde{O}}(k^{15})$ for sBanning tree distributions. Our reduction involves sampling from ${\widetilde{O}}(1)$ domain-sparsified distributions, all of which can be produced efficiently assuming approximate overestimates for marginals of $\mu$ are known and stored in a convenient data structure. Having access to marginals is the discrete analog of having access to the mean and covariance of a continuous distribution, or equivalently knowing “isotropy” for the distribution, the key behind optimal samplers in the continuous setting based on the famous Kannan-Lovász-Simonovits (KLS) conjecture. We view our result as analogous in spirit to the KLS conjecture and its consequences for sampling, but rather for discrete strongly Rayleigh measures.1Throughout, ${\widetilde{O}}(\cdot)$ hides polylogarithmic factors in n.

We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in $m^{1+o(1)}$ time. Our algorithm builds the flow through a sequence of $m^{1+o(1)}$ approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized $m^{o(1)}$ time using a new dynamic graph data structure. Our framework extends to algorithms running in $m^{1+o(1)}$ time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and p-norm isotonic regression on arbitrary directed acyclic graphs.

In this note, we design a discrete random walk on the real line which takes steps 0,±1 (and one with steps in {±1,2}) where at least 96% of the signs are ±1 in expectation, and which has 𝒩(0,1) as a stationary distribution. As an immediate corollary, we obtain an online version of Banaszczyk’s discrepancy result for partial colorings and ±1,2 signings. Additionally, we recover linear time algorithms for logarithmic bounds for the Komlós conjecture in an oblivious online setting.

We make several advances broadly related to the maintenance of electrical flows in weighted graphs undergoing dynamic resistance updates, including:

In this paper we obtain improved iteration complexities for solving ℓp regression. We provide methods which given any full-rank A ∈ ℝn × d with n ≥ d, b ∈ ℝn, and p ≥ 2 solve minx ∈ ℝd ||A x − b||p to high precision in time dominated by that of solving Op(dp−2/3p−2) linear systems in A⊤D A for positive diagonal matrices D. This improves upon the previous best iteration complexity of Op(np−2/3p−2) (Adil, Kyng, Peng, Sachdeva 2019). As a corollary, we obtain an O(d1/3є−2/3) iteration complexity for approximate ℓ∞ regression. Further, for q ∈ (1, 2] and dual norm q = p/(p−1) we provide an algorithm that solves ℓq regression in O(dp−2/2p−2) iterations.

We give an online algorithm that with high probability computes a (e/e−1 + o(1))Δ edge coloring on a graph G with maximum degree Δ = ω(logn) under online edge arrivals against oblivious adversaries, making first progress on the conjecture of Bar-Noy, Motwani, and Naor in this general setting. Our algorithm is based on reducing to a matching problem on locally treelike graphs, and then applying a tree recurrences based approach for arguing correlation decay.

We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrices to high accuracy. Our Laplacian solver has a round complexity of$O(n^{o(1)}(\sqrt{n}+D))$, and thus almost matches the lower bound of$\widetilde{\Omega}(\sqrt{n}+D)$, where$n$is the number of nodes in the network and$D$is its diameter. We show that our distributed solver yields new sublinear round algorithms for several cornerstone problems in combinatorial optimization. This is achieved by leveraging the powerful algorithmic framework of Interior Point Methods (IPMs) and the Laplacian paradigm in the context of distributed graph algorithms, which entails numerically solving optimization problems on graphs via a series of Laplacian systems. Problems that benefit from our distributed algorithmic paradigm include exact mincost flow, negative weight shortest paths, maxflow, and bipartite matching on sparse directed graphs. For the maxflow problem, this is the first exact distributed algorithm that applies to directed graphs, while the previous work by [Ghaffari et al. SICOMP'18] considered the approximate setting and works only for undirected graphs. For the mincost flow and the negative weight shortest path problems, our results constitute the first exact distributed algorithms running in a sublinear number of rounds. Given that the hybrid between IPMs and the Laplacian paradigm has proven useful for tackling numerous optimization problems in the centralized setting, we believe that our distributed solver will find future applications. At the heart of our distributed Laplacian solver is the notion of spectral subspace sparsifiers of [Li, Schild FOCS'18]. We present a nontrivial distributed implementation of their construction by (i) giving a parallel variant of their algorithm that avoids the sampling of random spanning trees and uses approximate leverage scores instead, and (ii) showing that the algorithm still produces a high-quality subspace spectral sparsifier by carefully setting up and analyzing matrix martingales. Combining this vertex reduction recursively with both tree and elimination-based preconditioners leads to our algorithm for solving Laplacian systems. The construction of the elimination-based preconditioners is based on computing short random walks, and we introduce a new technique for reducing the congestion incurred by the simulation of these walks on weighted graphs.

We give an algorithm for computing exact maximum flows on graphs with$m$edges and integer capacities in the range [$1,U$] in$\tilde{O}(m^{\frac{3}{2}-\frac{1}{328}}\log U)$time.11We use$\tilde{O}(\cdot)$to suppress logarithmic factors in$m$. For sparse graphs with polynomially bounded integer capacities, this is the first improvement over the$\tilde{O}(m^{1.5}\log U)$time bound from [Goldberg-Rao JACM '98]. Our algorithm revolves around dynamically maintaining the augmenting electrical flows at the core of the interior point method based algorithm from [Mądry JACM '16]. This entails designing data structures that, in limited settings, return edges with large electric energy in a graph undergoing resistance updates.

Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether (1 + ∊)-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter c, find a smaller graph, which we call connectivity-c mimicking network, which preserves connectivity among k terminals exactly up to the value of c. We show that connectivity-c mimicking networks with O(kc4) edges exist and can be found in time m(c log n)O(c). We also give a separate algorithm that constructs such graphs with k · O(c)2c edges in time mcO(c) logO(1) n. These results lead to the first data structures for answering fully dynamic offline c-edge-connectivity queries for c ≥ 4 in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.

We study discrepancy minimization for vectors in ℝn under various settings. The main result is the analysis of a new simple random process in high dimensions through a comparison argument. As corollaries, we obtain bounds which are tight up to logarithmic factors for online vector balancing against oblivious adversaries, resolving several questions posed by Bansal, Jiang, Singla, and Sinha (STOC 2020), as well as a linear time algorithm for logarithmic bounds for the Komlós conjecture.

In this paper we provide new randomized algorithms with improved runtimes for solving linear programs with two-sided constraints. In the special case of the minimum cost flow problem on n-vertex m-edge graphs with integer polynomially-bounded costs and capacities we obtain a randomized method which solves the problem in Õ(m + n1.5) time. This improves upon the previous best runtime of Õ(m √n) [Lee-Sidford’14] and, in the special case of unit-capacity maximum flow, improves upon the previous best runtimes of m4/3 + o(1) [Liu-Sidford’20, Kathuria’20] and Õ(m √n) [Lee-Sidford’14] for sufficiently dense graphs.

Abstract Interactive proofs of proximity allow a sublinear-time verifier to check that a given input is close to the language, using a small amount of communication with a powerful (but untrusted) prover. In this work, we consider two natural minimally interactive variants of such proofs systems, in which the prover only sends a single message, referred to as the proof. The first variant, known as -proofs of Proximity (), is fully non-interactive, meaning that the proof is a function of the input only. The second variant, known as -proofs of Proximity (), allows the proof to additionally depend on the verifier's (entire) random string. The complexity of both s and s is the total number of bits that the verifier observes—namely, the sum of the proof length and query complexity. Our main result is an exponential separation between the power of s and s. Specifically, we exhibit an explicit and natural property $$\Pi$$ Π that admits an with complexity $$O(\log n)$$ O ( log n ) , whereas any for $$\Pi$$ Π has complexity $$\tilde{\Omega}(n^{1/4})$$ Ω ~ ( n 1 / 4 ) , where n denotes the length of the input in bits. Our lower bound also yields an alternate proof, which is more general and arguably much simpler, for a recent result of Fischer et al. (ITCS, 2014). Also, Aaronson (Quantum Information & Computation 2012) has shown a $$\Omega(n^{1/6})$$ Ω ( n 1 / 6 ) lower bound for the same property $$\Pi$$ Π . Lastly, we also consider the notion of oblivious proofs of proximity, in which the verifier's queries are oblivious to the proof. In this setting, we show that s can only be quadratically stronger than s. As an application of this result, we show an exponential separation between the power of public and private coin for oblivious interactive proofs of proximity.

We present an algorithm, which given any m-edge n-vertex directed graph with positive integer capacities at most U computes a maximum s-t flow for any vertices s and t in O(m4/3+o(1)U1/3) time. This improves upon the previous best running times of O(m11/8+o(1)U1/4) [1], Õ(m√nlogU) [2] and O(mn) [3] when the graph is not too dense and doesn't have large capacities. We build upon advances for sparse maxflow based on interior point methods [1], [4], [5]. Whereas these methods increase the energy of local ℓ2-norm minimizing electrical flows, we instead increase the Bregman divergence value of flows which minimize the Bregman divergence with respect to a weighted log barrier. This allows us to trace the central path with progress depending only on ℓ∞norm bounds on the congestion vector as opposed to the ℓ4norm, which arises in these prior works. Further, we show that smoothed ℓ2-ℓpflows [6], [7] which were used to maximize energy [1] can also be used to efficiently maximize divergence, thereby yielding our desired runtimes. We believe our approach towards Bregman divergences of barriers may be of further interest.

In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given any submodular function defined on n-elements with range [–1, 1], computes an ε-additive approximate minimizer in Õ(n/ε2) oracle evaluations with high probability. This improves over the Õ(n5/3/ε2) oracle evaluation algorithm of Chakrabarty et al. (STOC 2017) and the Õ(n3/2/ε2) oracle evaluation algorithm of Hamoudi et al… Further, we leverage a generalization of this result to obtain efficient algorithms for minimizing a broad class of nonconvex functions. For any function f with domain [0, 1]n that satisfies for all i ≠ j and is L-Lipschitz with respect to the L∞-norm we give an algorithm that computes an ε-additive approximate minimizer with Õ(n · poly(L/ε) function evaluation with high probability.

In this paper we provide a Õ(m√n) time algorithm that computes a 3-multiplicative approximation of the girth of a n-node m-edge directed graph with non-negative edge lengths. This is the first algorithm which approximates the girth of a directed graph up to a constant multiplicative factor faster than All-Pairs Shortest Paths (APSP) time, i.e. O(mn). Additionally, for any integer k ≥ 1, we provide a deterministic algorithm for a O(kloglogn)-multiplicative approximation to the girth in directed graphs in Õ(m 1+1/k ) time. Combining the techniques from these two results gives us an algorithm for a O(klogk)-multiplicative approximation to the girth in directed graphs in Õ(m 1+1/k ) time. Our results naturally also provide algorithms for improved constructions of roundtrip spanners, the analog of spanners in directed graphs.

In this paper we provide an algorithm which given any m-edge n-vertex directed graph with integer capacities at most U computes a maximum s-t flow for any vertices s and t in m 11/8+o(1) U 1/4 time with high probability. This running time improves upon the previous best of Õ(m 10/7 U 1/7) (Mądry 2016), Õ(m √n logU) (Lee Sidford 2014), and O(mn) (Orlin 2013) when the graph is not too dense or has large capacities.

In this paper we provide a parallel algorithm that given any n-node m-edge directed graph and source vertex s computes all vertices reachable from s with Õ(m) work and n{1/2+o(1)} depth with high probability in n. This algorithm also computes a set of Õ(n) edges which when added to the graph preserves reachability and ensures that the diameter of the resulting graph is at most n{1/2+o(1)}. Our result improves upon the previous best known almost linear work reachability algorithm due to Fineman [1] which had depth Õ(n2/3). Further, we show how to leverage this algorithm to achieve improved distributed algorithms for single source reachability in the CONGEST model. In particular, we provide a distributed algorithm that given a n-node digraph of undirected hop-diameter D solves the single source reachability problem with Õ(n1/2+ n1/3+o(1)D2/3) rounds of the communication in the CONGEST model with high probability in n. Our algorithm is nearly optimal whenever D = O(n1/4-ε) for any constant ε > 0 and is the first nearly optimal algorithm for general graphs whose diameter is Ω(nδ) for any constant δ.

A curious property of randomized log-space search algorithms is that their outputs are often longer than their workspace. This leads to the question: how can we reproduce the results of a randomized log space computation without storing the output or randomness verbatim? Running the algorithm again with new random bits may result in a new (and potentially different) output. We show that every problem in search-RL has a randomized log-space algorithm where the output can be reproduced. Specifically, we show that for every problem in search-RL, there are a pair of log-space randomized algorithms A and B where for every input x, A will output some string tx of size O(log n), such that B when running on (x, tx) will be pseudo-deterministic: that is, running B multiple times on the same input (x, tx) will result in the same output on all executions with high probability. Thus, by storing only O(log n) bits in memory, it is possible to reproduce the output of a randomized log-space algorithm. An algorithm is reproducible without storing any bits in memory (i.e., |tx| = 0) if and only if it is pseudo-deterministic. We show pseudo-deterministic algorithms for finding paths in undirected graphs and Eulerian graphs using logarithmic space. Our algorithms are substantially faster than the best known deterministic algorithms for finding paths in such graphs in log-space. The algorithm for search-RL has the additional property that its output, when viewed as a random variable depending on the randomness used by the algorithm, has entropy O(log n).

We present improved algorithms for short cycle decomposition of a graph – a decomposition of an undirected, unweighted graph into edge-disjoint cycles, plus a small number of additional edges. Short cycle decompositions were introduced in the recent work of Chu et al. (FOCS 2018), and were used to make progress on several questions in graph sparsification. For all constants δ ∊ (0, 1], we give an O(mnδ) time algorithm that, given a graph G, partitions its edges into cycles of length , with O(n) extra edges not in any cycle. This gives the first subquadratic, in fact almost linear time, algorithm achieving polylogarithmic cycle lengths. We also give an m · time algorithm that partitions the edges of a graph into cycles of length , with O(n) extra edges not in any cycle. This improves on the short cycle decomposition algorithms given by Chu et al. in terms of all parameters, and is significantly simpler. As a result, we obtain faster algorithms and improved guarantees for several problems in graph sparsification – construction of resistance sparsifiers, graphical spectral sketches, degree preserving sparsifiers, and approximating the effective resistances of all edges.