Arrow Research search

Author name cluster

Yinzhan Xu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers
2 author rows

Possible papers

23

ICML Conference 2025 Conference Paper

Breaking the n1. 5 Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition

  • Anders Aamand
  • Justin Y. Chen
  • Mina Dalirrooyfard
  • Slobodan Mitrovic
  • Yuriy Nevmyvaka
  • Sandeep Silwal
  • Yinzhan Xu

We study differentially private algorithms for graph cut sparsification, a fundamental problem in algorithms, privacy, and machine learning. While significant progress has been made, the best-known private and efficient cut sparsifiers on $n$-node graphs approximate each cut within $\widetilde{O}(n^{1. 5})$ additive error and $1+\gamma$ multiplicative error for any $\gamma > 0$ [Gupta, Roth, Ullman TCC’12]. In contrast, inefficient algorithms, i. e. , those requiring exponential time, can achieve an $\widetilde{O}(n)$ additive error and $1+\gamma$ multiplicative error [Eliáš, Kapralov, Kulkarni, Lee SODA’20]. In this work, we break the $n^{1. 5}$ additive error barrier for private and efficient cut sparsification. We present an $(\varepsilon, \delta)$-DP polynomial time algorithm that, given a non-negative weighted graph, outputs a private synthetic graph approximating all cuts with multiplicative error $1+\gamma$ and additive error $n^{1. 25 + o(1)}$ (ignoring dependencies on $\varepsilon, \delta, \gamma$). At the heart of our approach lies a private algorithm for expander decomposition, a popular and powerful technique in (non-private) graph algorithms.

Details

NeurIPS Conference 2025 Conference Paper

Differentially Private Gomory-Hu Trees

  • Anders Aamand
  • Justin Chen
  • Mina Dalirrooyfard
  • Slobodan Mitrovic
  • Yuriy Nevmyvaka
  • Sandeep Silwal
  • Yinzhan Xu

Given an undirected, weighted $n$-vertex graph $G = (V, E, w)$, a Gomory-Hu tree $T$ is a weighted tree on $V$ that preserves the Min-$s$-$t$-Cut between any pair of vertices $s, t \in V$. Finding cuts in graphs is a key primitive in problems such as bipartite matching, spectral and correlation clustering, and community detection. We design a differentially private (DP) algorithm that computes an approximate Gomory-Hu tree. Our algorithm is $\varepsilon$-DP, runs in polynomial time, and can be used to compute $s$-$t$ cuts that are $\tilde{O}(n/\varepsilon)$-additive approximations of the Min-$s$-$t$-Cuts in $G$ for all distinct $s, t \in V$ with high probability. Our error bound is essentially optimal, since [Dalirrooyfard, Mitrovic and Nevmyvaka, Neurips 2023] showed that privately outputting a single Min-$s$-$t$-Cut requires $\Omega(n)$ additive error even with $(\varepsilon, \delta)$-DP and allowing for multiplicative error. Prior to our work, the best additive error bounds for approximate all-pairs Min-$s$-$t$-Cuts were $O(n^{3/2}/\varepsilon)$ for $\varepsilon$-DP [Gupta, Roth, Ullman, TCC 2009] and $\tilde{O}(\sqrt{mn}/ \varepsilon)$ for $(\varepsilon, \delta)$-DP [Liu, Upadhyay and Zou, SODA 2024], both achieved by DP algorithms that preserve all cuts in the graph. To achieve our result, we develop an $\varepsilon$-DP algorithm for the Minimum Isolating Cuts problem with near-linear error, and introduce a novel privacy composition technique combining elements of both parallel and basic composition to handle `bounded overlap' computational branches in recursive algorithms, which maybe of independent interest.

PDF Details

STOC Conference 2025 Conference Paper

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence

  • Jakob Nogler
  • Adam Polak 0001
  • Barna Saha
  • Virginia Vassilevska Williams
  • Yinzhan Xu
  • Christopher Ye 0001

The tree edit distance (TED) between two rooted ordered trees with n nodes labeled from an alphabet Σ is the minimum cost of transforming one tree into the other by a sequence of valid operations consisting of insertions, deletions and relabeling of nodes. The tree edit distance is a well-known generalization of string edit distance and has been studied since the 1970s. Its running time has seen steady improvements starting with an O ( n 6 ) algorithm [Tai, J.ACM 1979], improved to O ( n 4 ) [Shasha, Zhang, SICOMP 1989] and to O ( n 3 log n ) [Klein, ESA 1998], and culminating in an O ( n 3 ) algorithm [Demaine, Mozes, Rossman, Weimann, ACM TALG 2010]. The latter is known to be optimal for any dynamic programming based algorithm that falls under a certain decomposition framework that captures all known sub- n 4 time algorithms. Fine-grained complexity casts further light onto this hardness showing that a truly subcubic time algorithm for TED implies a truly subcubic time algorithm for All-Pairs Shortest Paths (APSP) [Bringmann, Gawrychowski, Mozes, Weimann, ACM TALG 2020]. Therefore, under the popular APSP hypothesis, a truly subcubic time algorithm for TED cannot exist. However, unlike many problems in fine-grained complexity for which conditional hardness based on APSP also comes with equivalence to APSP, whether TED can be reduced to APSP has remained unknown. In this paper, we resolve this. Not only we show that TED is fine-grained equivalent to APSP, our reduction is tight enough, so that combined with the fastest APSP algorithm to-date [Williams, SICOMP 2018] it gives the first ever subcubic time algorithm for TED running in n 3 /2 Ω(√log n ) time. We also consider the unweighted tree edit distance problem in which the cost of each edit (insertion, deletion, and relabeling) is one. For unweighted TED, a truly subcubic algorithm is known due to Mao [Mao, FOCS 2022], and later improved slightly by Dürr [Dürr, IPL 2023] to run in O ( n 2.9148 ) time. Since their algorithm uses bounded monotone min-plus product as a crucial subroutine, and the best running time for this product is Õ( n 3+ω/2 )≤ O ( n 2.6857 ) (where ω is the exponent of fast matrix multiplication), the much higher running time of unweighted TED remained unsatisfactory. In this work, we close this gap and give an algorithm for unweighted TED that runs in Õ( n 3+ω/2 ) time.

Details

SODA Conference 2024 Conference Paper

New Bounds for Matrix Multiplication: from Alpha to Omega

  • Virginia Vassilevska Williams
  • Yinzhan Xu
  • Zixuan Xu
  • Renfei Zhou

The main contribution of this paper is a new improved variant of the laser method for designing matrix multiplication algorithms. Building upon the recent techniques of [Duan, Wu, Zhou, FOCS 2023], the new method introduces several new ingredients that not only yield an improved bound on the matrix multiplication exponent ω, but also improve the known bounds on rectangular matrix multiplication by [Le Gall and Urrutia, SODA 2018]. In particular, the new bound on ω is ω ≤ 2. 371552 (improved from ω ≤ 2. 371866). For the dual matrix multiplication exponent α defined as the largest α for which ω(1, α, 1) = 2, we obtain the improvement α ≥ 0. 321334 (improved from α ≥ 0. 31389). Similar improvements are obtained for various other exponents for multiplying rectangular matrices.

Details

STOC Conference 2024 Conference Paper

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More

  • Ce Jin 0001
  • Yinzhan Xu

In sparse convolution-type problems, a common technique is to hash the input integers modulo a random prime p ∈ [ Q /2, Q ] for some parameter Q , which reduces the range of the input integers while preserving their additive structure. However, this hash family suffers from two drawbacks, which led to bottlenecks in many state-of-the-art algorithms: (1) The collision probability of two elements from [ N ] is O (log N / Q ) rather than O (1/ Q ); (2) It is difficult to derandomize the choice of p ; known derandomization techniques lead to super-logarithmic overhead [Chan, Lewenstein STOC’15]. In this paper, we partially overcome these drawbacks in certain scenarios, via novel applications of the large sieve inequality from analytic number theory. Consequently, we obtain the following improved algorithms for various problems (in the standard word RAM model): Sparse Nonnegative Convolution: We obtain an O ( t log t )-time Las Vegas algorithm that computes the convolution A ⋆ B of two nonnegative integer vectors A , B , where t is the output sparsity || A ⋆ B || 0 . Moreover, our algorithm terminates in O ( t log t ) time with 1−1/ poly ( t ) probability. This simultaneously improves the O ( t log t loglog t )-time Las Vegas algorithm [Bringmann, Fischer, Nakos SODA’22] and the Monte Carlo O ( t log t )-time algorithm with failure probability 2 −√log t [Bringmann, Fischer, Nakos STOC’21]. Text-to-Pattern Hamming Distances: Given a length- m pattern P and a length- n text T , we obtain an O ( n √ m loglog m )-time deterministic algorithm that exactly computes the Hamming distance between P and every length- m substring of T . This improves the previous O ( n √ m (log m loglog m ) 1/4 )-time deterministic algorithm [Chan, Jin, Vassilevska Williams, Xu FOCS’23] and nearly matches their O ( n √ m )-time Las Vegas algorithm. Sparse General Convolution: For sparse convolution with possibly negative input, all previous approaches required Ω( t log 2 t ) time, where t is the maximum of input and output sparsity, and an important question left open by [Bringmann, Fischer, Nakos STOC’21] is whether this can be improved. We make partial progress towards solving this question by giving a Monte Carlo O ( t log t ) time algorithm in the restricted case where the length N of the input vectors satisfies N ≤ t 1.99 .

Details

SODA Conference 2024 Conference Paper

Simpler and Higher Lower Bounds for Shortcut Sets

  • Virginia Vassilevska Williams
  • Yinzhan Xu
  • Zixuan Xu

We study the well-known shortcut set problem: how much can one decrease the diameter of a directed graph by adding a small set of shortcuts from the transitive closure of the graph. We provide a variety of lower bounds. First, we vastly simplify the recent construction of Bodwin and Hoppenworth [FOCS 2023] which showed an lower bound for the diameter of a directed unweighted n -node graph after adding O(n) shortcut edges. We highlight that our simplification completely removes the use of the convex sets by Bárány and Larman [Math. Ann. 1998] used in all previous lower bound constructions. Our simplification also removes the need for randomness and further removes some log factors. It allows us to generalize the construction to higher dimensions, which in turn can be used to show the following results: • There is an Ω( n 1/5 ) lower bound for the diameter of the graph after adding O(m) shortcuts, where m denotes the number of edges in the input graph. • For all ɛ > 0, there exists a δ > 0 such that there are n -vertex O ( n )-edge graphs G where adding any shortcut set of size O(n 2-ɛ ) keeps the diameter of G at Ω( n δ ). This improves the sparsity of the constructed graph compared to a known similar result by Hesse [SODA 2003]. • For any integer d ≥ 2, there exists a graph G = ( V, E ) on n vertices and S ⊆ V with, such that when adding O ( n ) or O ( m ) shortcuts, the sourcewise diameter (the largest distance from some vertex in S to some reachable vertex in the graph) is. This initiates the study of sourcewise diameter in the setting of the shortcut set problem; previously, the study of the sourcewise variant is popular in a wide variety of related problems such as spanners and distance preservers. Complementing this lower bound result, we also provide an upper bound: we show that, we can reduce the sourcewise diameter to by adding O ( n ) shortcut edges. * Massachusetts Institute of Technology. Supported by NSF Grants CCF-2129139 and CCF-2330048 and BSF Grant 2020356.

Details

STOC Conference 2024 Conference Paper

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques

  • Mina Dalirrooyfard
  • Surya Mathialagan
  • Virginia Vassilevska Williams
  • Yinzhan Xu

We study the problem of finding and listing k -cliques in an m -edge, n -vertex graph, for constant k ≥ 3. This is a fundamental problem of both theoretical and practical importance. Our first contribution is an algorithmic framework for finding k -cliques that gives the first improvement in 19 years over the old runtimes for 4 and 5-clique finding, as a function of m [Eisenbrand and Grandoni, TCS’04]. With the current bounds on matrix multiplication, our algorithms run in O ( m 1.66 ) and O ( m 2.06 ) time, respectively, for 4-clique and 5-clique finding. Our main contribution is an output-sensitive algorithm for listing k -cliques, for any constant k ≥ 3. We complement the algorithm with tight lower bounds based on standard fine-grained assumptions. Previously, the only known conditionally optimal output-sensitive algorithms were for the case of 3-cliques given by Bj'orklund, Pagh, Vassilevska W. and Zwick [ICALP’14]. If the matrix multiplication exponent ω is 2, and if the number of k -cliques t is large enough, the running time of our algorithms is Õ(min{ m 1/ k −2 t 1 − 2/ k ( k −2) , n 2/ k −1 t 1−2/ k ( k −1) }), and this is tight under the Exact- k -Clique Hypothesis. This running time naturally extends the running time obtained by Bj'orklund, Pagh, Vassilevska W. and Zwick for k =3. Our framework is very general in that it gives k -clique listing algorithms whose running times can be measured in terms of the number of ℓ-cliques Δ ℓ in the graph for any 1≤ ℓ< k . This generalizes the typical parameterization in terms of n (the number of 1-cliques) and m (the number of 2-cliques). If ω is 2, and if the size of the output, Δ k , is sufficiently large, then for every ℓ< k , the running time of our algorithm for listing k -cliques is Õ(Δ ℓ 2/ℓ ( k − ℓ) Δ k 1−2/ k ( k −ℓ) ). We also show that this runtime is optimal for all 1 ≤ ℓ < k under the Exact k -Clique hypothesis.

Details

SODA Conference 2023 Conference Paper

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds

  • Justin Y. Chen
  • Badih Ghazi
  • Ravi Kumar 0001
  • Pasin Manurangsi
  • Shyam Narayanan
  • Jelani Nelson
  • Yinzhan Xu

We study the problem of releasing the weights of all-pairs shortest paths in a weighted undirected graph with differential privacy (DP). In this setting, the underlying graph is fixed and two graphs are neighbors if their edge weights differ by at most 1 in the ℓ 1 -distance. We give an algorithm with additive error Õ ( n 2/3 /ε) in the ε-DP case and an algorithm with additive error in the (ε, δ)-DP case, where n denotes the number of vertices. This positively answers a question of Sealfon [Sea16, Sea20], who asked whether a o ( n )- error algorithm exists. We also show that an additive error of Ω ( n 1/6 ) is necessary for any sufficiently small ε, δ > 0. Furthermore, we show that if the graph is promised to have reasonably bounded weights, one can improve the error further to roughly in the ε-DP case and roughly in the (ε, δ)-DP case. Previously, it was only known how to obtain Õ ( n 2/3 /ε 1/3 ) additive error in the ε-DP case and additive error in the (ε, δ)-DP case for bounded-weight graphs [Sea16]. Finally, we consider a relaxation where a multiplicative approximation is allowed. We show that, with a multiplicative approximation factor k, the additive error can be reduced to Õ( n 1/2+ O (1/ k ) /ε) in the ε-DP case and Õ ( n 1/3+O(1/ k ) /ε) in the (ε, δ)-DP case.

Details

FOCS Conference 2023 Conference Paper

Faster Algorithms for Text-to-Pattern Hamming Distances

  • Timothy M. Chan
  • Ce Jin 0001
  • Virginia Vassilevska Williams
  • Yinzhan Xu

We study the classic Text-to-Pattern Hamming Distances problem: given a pattern P of length m and a text T of length n, both over a polynomial-size alphabet, compute the Hamming distance between P and $T[i \ldots i+m-1]$ for every shift i, under the standard Word-RAM model with $\Theta(\log n)$-bit words. •We provide an $O(n \sqrt{m})$ time Las Vegas randomized algorithm for this problem, beating the decades-old $O(n \sqrt{m \log m})$ running time [Abrahamson, SICOMP 1987]. We also obtain a deterministic algorithm, with a slightly higher $O\left(n \sqrt{m}(\log m \log \log m)^{1 / 4}\right)$ running time. Our randomized algorithm extends to the k-bounded setting, with running time $O\left(n+\frac{n k}{\sqrt{m}}\right)$, removing all the extra logarithmic factors from earlier algorithms [Gawrychowski and Uznanski, ICALP 2018; Chan, Golan, Kociumaka, Kopelowitz and Porat, STOC 2020]. •For the $(1+\varepsilon)$-approximate version of Text-to-Pattern Hamming Distances, we give an $\widetilde{O}\left(\varepsilon^{-0. 93} n\right)$ time Monte Carlo randomized algorithm (where $\widetilde{O}$ hides poly-logarithmic factors), beating the previous $\widetilde{O}\left(\varepsilon^{-1} n\right)$ running time [Kopelowitz and Porat, FOCS 2015; Kopelowitz and Porat, SOSA 2018]. Our approximation algorithm exploits a connection with 3SUM, and uses a combination of Fredman’s trick, equality matrix product, and random sampling; in particular, we obtain new results on approximate counting versions of 3 SUM and Exact Triangle, which may be of independent interest. Our exact algorithms use a novel combination of hashing, bit-packed FFT, and recursion; in particular, we obtain a faster algorithm for computing the sumset of two integer sets, in the regime when the universe size is close to quadratic in the number of elements. We also prove a fine-grained equivalence between the exact Text-to-Pattern Hamming Distances problem and a range-restricted, counting version of 3 SUM.

Details

STOC Conference 2023 Conference Paper

Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More

  • Timothy M. Chan
  • Virginia Vassilevska Williams
  • Yinzhan Xu

In this paper we carefully combine Fredman’s trick [SICOMP’76] and Matoušek’s approach for dominance product [IPL’91] to obtain powerful results in fine-grained complexity. Under the hypothesis that APSP for undirected graphs with edge weights in {1, 2, …, n } requires n 3− o (1) time (when ω=2), we show a variety of conditional lower bounds, including an n 7/3− o (1) lower bound for unweighted directed APSP and an n 2.2− o (1) lower bound for computing the Minimum Witness Product between two n × n Boolean matrices, even if ω=2, improving upon their trivial n 2 lower bounds. Our techniques can also be used to reduce the unweighted directed APSP problem to other problems. In particular, we show that (when ω = 2), if unweighted directed APSP requires n 2.5− o (1) time, then Minimum Witness Product requires n 7/3− o (1) time. We show that, surprisingly, many central problems in fine-grained complexity are equivalent to their natural counting versions. In particular, we show that Min-Plus Product and Exact Triangle are subcubically equivalent to their counting versions, and 3SUM is subquadratically equivalent to its counting version. We also obtain new algorithms using new variants of the Balog-Szemerédi-Gowers theorem from additive combinatorics. For example, we get an O ( n 3.83 ) time deterministic algorithm for exactly counting the number of shortest paths in an arbitrary weighted graph, improving the textbook O ( n 4 ) time algorithm. We also get faster algorithms for 3SUM in preprocessed universes, and deterministic algorithms for 3SUM on monotone sets in {1, 2, …, n } d .

Details

STOC Conference 2023 Conference Paper

Optimal Bounds for Noisy Sorting

  • Yuzhou Gu
  • Yinzhan Xu

Sorting is a fundamental problem in computer science. In the classical setting, it is well-known that (1± o (1)) n log 2 n comparisons are both necessary and sufficient to sort a list of n elements. In this paper, we study the Noisy Sorting problem, where each comparison result is flipped independently with probability p for some fixed p ∈ (0, 1/2). As our main result, we show that (1± o (1)) ( 1/ I ( p ) + 1/(1−2 p ) log 2 (1− p / p ) ) n log 2 n noisy comparisons are both necessary and sufficient to sort n elements with error probability o (1) using noisy comparisons, where I ( p )=1 + p log 2 p +(1− p )log 2 (1− p ) is capacity of BSC channel with crossover probability p . This simultaneously improves the previous best lower and upper bounds (Wang, Ghaddar and Wang, ISIT 2022) for this problem.

Details

STOC Conference 2023 Conference Paper

Removing Additive Structure in 3SUM-Based Reductions

  • Ce Jin 0001
  • Yinzhan Xu

Our work explores the hardness of 3SUM instances without certain additive structures, and its applications. As our main technical result, we show that solving 3SUM on a size- n integer set that avoids solutions to a + b = c + d for { a , b } ≠ { c , d } still requires n 2− o (1) time, under the 3SUM hypothesis. Such sets are called Sidon sets and are well-studied in the field of additive combinatorics. Combined with previous reductions, this implies that the All-Edges Sparse Triangle problem on n -vertex graphs with maximum degree √ n and at most n k /2 k -cycles for every k ≥ 3 requires n 2− o (1) time, under the 3SUM hypothesis. This can be used to strengthen the previous conditional lower bounds by Abboud, Bringmann, Khoury, and Zamir [STOC’22] of 4-Cycle Enumeration, Offline Approximate Distance Oracle and Approximate Dynamic Shortest Path. In particular, we show that no algorithm for the 4-Cycle Enumeration problem on n -vertex m -edge graphs with n o (1) delays has O ( n 2−ε ) or O ( m 4/3−ε ) pre-processing time for ε >0. We also present a matching upper bound via simple modifications of the known algorithms for 4-Cycle Detection. A slight generalization of the main result also extends the result of Dudek, Gawrychowski, and Starikovskaya [STOC’20] on the 3SUM hardness of nontrivial 3-Variate Linear Degeneracy Testing (3-LDTs): we show 3SUM hardness for all nontrivial 4-LDTs. The proof of our main technical result combines a wide range of tools: Balog-Szemerédi-Gowers theorem, sparse convolution algorithm, and a new almost-linear hash function with almost 3-universal guarantee for integers that do not have small-coefficient linear relations.

Details

FOCS Conference 2022 Conference Paper

Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure

  • Virginia Vassilevska Williams
  • Eyob Woldeghebriel
  • Yinzhan Xu

This paper considers a natural fault-tolerant shortest paths problem: for some constant integer f, given a directed weighted graph with no negative cycles and two fixed vertices s and t, compute (either explicitly or implicitly) for every tuple of f edges, the distance from s to t if these edges fail. We call this problem f-Fault Replacement Paths (f FRP). We first present an $\tilde{O}(n^{3}$) time algorithm for 2FRP in n-vertex directed graphs with arbitrary edge weights and no negative cycles. As 2FRP is a generalization of the well-studied Replacement Paths problem (RP) that asks for the distances between s and t for any single edge failure, 2FRP is at least as hard as RP. Since RP in graphs with arbitrary weights is equivalent in a fine-grained sense to All-Pairs Shortest Paths (APSP) [Vassilevska Williams and Williams FOCS’10, J. ACM’18], 2FRP is at least as hard as APSP, and thus a substantially subcubic time algorithm in the number of vertices for 2FRP would be a breakthrough. Therefore, our algorithm in $\tilde{O}(n^{3})$ time is conditionally nearly optimal. Our algorithm immediately implies an $\tilde{O}(n^{f+1})$ time algorithm for the more general f FRP problem, giving the first improvement over the straightforward $O(n^{f+2})$ time algorithm. Then we focus on the restriction of 2FRP to graphs with small integer weights bounded by M in absolute values. We show that similar to $\mathrm{R}\mathrm{P}, 2\mathrm{F}\mathrm{R}\mathrm{P}$ has a substantially subcubic time algorithm for small enough M. Using the current best algorithms for rectangular matrix multiplication, we obtain a randomized algorithm that runs in $\tilde{O}(M^{2/3}n^{2. 9153})$ time. This immediately implies an improvement over our $\tilde{O}(n^{f+1})$ time arbitrary weight algorithm for all $f\gt1$. We also present a data structure variant of the algorithm that can trade off pre-processing and query time. In addition to the algebraic algorithms, we also give an $n^{8/3-o(1)}$ conditional lower bound for combinatorial 2FRP algorithms in directed unweighted graphs, and more generally, combinatorial lower bounds for the data structure version of $fF\mathrm{R}\mathrm{P}$.

Details

STOC Conference 2022 Conference Paper

Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV

  • Timothy M. Chan
  • Virginia Vassilevska Williams
  • Yinzhan Xu

The 3SUM hypothesis, the All-Pairs Shortest Paths (APSP) hypothesis and the Strong Exponential Time Hypothesis are the three main hypotheses in the area of fine-grained complexity. So far, within the area, the first two hypotheses have mainly been about integer inputs in the Word RAM model of computation. The “Real APSP” and “Real 3SUM” hypotheses, which assert that the APSP and 3SUM hypotheses hold for real-valued inputs in a reasonable version of the Real RAM model, are even more believable than their integer counterparts.

Details

IJCAI Conference 2022 Conference Paper

Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules

  • Krzysztof Sornat
  • Virginia Vassilevska Williams
  • Yinzhan Xu

We present an almost optimal algorithm for the classic Chamberlin-Courant multiwinner voting rule (CC) on single-peaked preference profiles. Given n voters and m candidates, it runs in almost linear time in the input size improving the previous best O(nm^2) time algorithm. We also study multiwinner voting rules on nearly single-peaked preference profiles in terms of the candidate-deletion operation. We show a polynomial-time algorithm for CC where a given candidate-deletion set D has logarithmic size. Actually, our algorithm runs in 2^|D| * poly(n, m) time and the base of the power cannot be improved under the Strong Exponential Time Hypothesis. We also adapt these results to all non-constant Thiele rules which generalize CC with approval ballots.

PDF Details DOI

STOC Conference 2022 Conference Paper

Tight dynamic problem lower bounds from generalized BMM and OMv

  • Ce Jin 0001
  • Yinzhan Xu

Popular fine-grained hypotheses have been successful in proving conditional lower bounds for many dynamic problems. Two of the most widely applicable hypotheses in this context are the combinatorial Boolean Matrix Multiplication (BMM) hypothesis and the closely-related Online Matrix Vector Multiplication (OMv) hypothesis . The main theme of this paper is using k -dimensional generalizations of these two hypotheses to prove new tight conditional lower bounds for dynamic problems.

Details

FOCS Conference 2020 Conference Paper

Monochromatic Triangles, Triangle Listing and APSP

  • Virginia Vassilevska Williams
  • Yinzhan Xu

All-Pairs Shortest Paths (APSP) is one of the most basic problems in graph algorithms. Given an n-node directed or undirected graph with integer weights in {-n c, .. ., n c } and no negative cycles, APSP asks to compute the shortest paths distance between every pair of vertices. The fastest known algorithm for APSP runs in n 3 /2 Θ(√{logn}) time [Williams'14], and no truly subcubic time algorithms are known. One of the main hypotheses in fine-grained complexity is that APSP requires n 3-o(1) time. Another famous hypothesis in fine-grained complexity is that the 3SUM problem for n integers (which can be solved in O(n 2 ) time) requires n 2-o(1) time. Although there are no direct reductions between 3SUM and APSP, it is known that they are related: the (min, +)-convolution problem reduces in a fine-grained way to both, and both fine-grained reduce to the Exact Triangle problem. In this paper we find more relationships between these two problems and other basic problems. Pătraşcu had shown that under the 3SUM hypothesis the All-Edges Sparse Triangle problem in m-edge graphs requires m 4/3-o(1) time. The latter problem asks to determine for every edge e, whether e is in a triangle. It is equivalent to the problem of listing m triangles in an m-edge graph where m=-Õ(n 1. 5 ), and can be solved in O(m 1. 41 ) time [Alon et al. '97] with the current matrix multiplication bounds, and in Õ(m 4/3 ) time if ω = 2. We show that one can reduce Exact Triangle to All-Edges Sparse Triangle, showing that All-Edges Sparse Triangle (and hence Triangle Listing) requires m 4/3-o(1) time also assuming the APSP hypothesis. This allows us to provide APSP-hardness for many dynamic problems that were previously known to be hard under the 3SUM hypothesis. We also consider the All-Edges Monochromatic Triangle problem. Via work of [Lincoln et al. '20], our result on All-Edges Sparse Triangle implies that if the All-Edges Monochromatic Triangle problem has an O(n 2. 5-ε ) time algorithm for, then both the APSP and 3SUM hypotheses are false. The fastest algorithm for All-Edges Monochromatic Triangle runs in Õ(n (3+ω)/2 ) time [Vassilevska et al. '06], and our new reduction shows that if ω = 2, this algorithm is best possible, unless 3SUM or APSP can be solved faster. Besides 3SUM, previously the only problems known to be fine-grained reducible to All-Edges Monochromatic Triangle were the seemingly easier problems directed unweighted APSP and Min-Witness Product [Lincoln et al. '20]. Our reduction shows that this problem is much harder. We also connect the problem to other “intermediate” problems, whose runtimes are between O(n ω ) and O(n 3 ), such as the Max-Min product problem.

Details
v2026.09.13