We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An Õ(n^{ω+3}a+n⁴a²+n^ωlog(1/ε)) time algorithm for finding an εapproximation to the Jordan Normal form of an integer matrix with abit entries, where ω is the exponent of matrix multiplication. (2) An Õ(n⁶d⁶a+n⁴d⁴a²+n³d³log(1/ε)) time algorithm for εapproximately computing the spectral factorization P(x) = Q^*(x)Q(x) of a given monic n× n rational matrix polynomial of degree 2d with rational abit coefficients having abit common denominators, which satisfies P(x)⪰0 for all real x. The first algorithm is used as a subroutine in the second one.
Despite its being of central importance, polynomial complexity bounds were not previously known for spectral factorization, and for Jordan form the best previous best running time was an unspecified polynomial in n of degree at least twelve [Cai, 1994]. Our algorithms are simple and judiciously combine techniques from numerical and symbolic computation, yielding significant advantages over either approach by itself.
more »
« less
This content will become publicly available on January 1, 2025
Fast Approximate Counting of Cycles
We consider the problem of approximate counting of triangles and longer fixed length cycles in directed graphs. For triangles, Tětek [ICALP'22] gave an algorithm that returns a (1±ε)approximation in Õ(n^ω/t^{ω2}) time, where t is the unknown number of triangles in the given n node graph and ω < 2.372 is the matrix multiplication exponent. We obtain an improved algorithm whose running time is, within polylogarithmic factors the same as that for multiplying an n× n/t matrix by an n/t × n matrix. We then extend our framework to obtain the first nontrivial (1± ε)approximation algorithms for the number of hcycles in a graph, for any constant h ≥ 3. Our running time is Õ(MM(n,n/t^{1/(h2)},n)), the time to multiply n × n/(t^{1/(h2)}) by n/(t^{1/(h2)) × n matrices.
Finally, we show that under popular finegrained hypotheses, this running time is optimal.
more »
« less
 Award ID(s):
 2330048
 NSFPAR ID:
 10524467
 Editor(s):
 Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola
 Publisher / Repository:
 Schloss Dagstuhl – LeibnizZentrum für Informatik
 Date Published:
 Volume:
 297
 ISSN:
 18688969
 ISBN:
 9783959773225
 Page Range / eLocation ID:
 297297
 Subject(s) / Keyword(s):
 Approximate triangle counting Approximate cycle counting Fast matrix multiplication Fast rectangular matrix multiplication Mathematics of computing → Approximation algorithms Mathematics of computing → Graph algorithms
 Format(s):
 Medium: X Size: 20 pages; 1118518 bytes Other: application/pdf
 Size(s):
 20 pages 1118518 bytes
 Right(s):
 Creative Commons Attribution 4.0 International license; info:eurepo/semantics/openAccess
 Sponsoring Org:
 National Science Foundation
More Like this


We consider the problem of spaceefficiently estimating the number of simplices in a hypergraph stream. This is the most natural hypergraph generalization of the highlystudied problem of estimating the number of triangles in a graph stream. Our input is a kuniform hypergraph H with n vertices and m hyperedges, each hyperedge being a ksized subset of vertices. A ksimplex in H is a subhypergraph on k+1 vertices X such that all k+1 possible hyperedges among X exist in H. The goal is to process the hyperedges of H, which arrive in an arbitrary order as a data stream, and compute a good estimate of T_k(H), the number of ksimplices in H. We design a suite of algorithms for this problem. As with trianglecounting in graphs (which is the special case k = 2), sublinear space is achievable but only under a promise of the form T_k(H) ≥ T. Under such a promise, our algorithms use at most four passes and together imply a space bound of O(ε^{2} log δ^{1} polylog n ⋅ min{(m^{1+1/k})/T, m/(T^{2/(k+1)})}) for each fixed k ≥ 3, in order to guarantee an estimate within (1±ε)T_k(H) with probability ≥ 1δ. We also give a simpler 1pass algorithm that achieves O(ε^{2} log δ^{1} log n⋅ (m/T) (Δ_E + Δ_V^{11/k})) space, where Δ_E (respectively, Δ_V) denotes the maximum number of ksimplices that share a hyperedge (respectively, a vertex), which generalizes a previous result for the k = 2 case. We complement these algorithmic results with space lower bounds of the form Ω(ε^{2}), Ω(m^{1+1/k}/T), Ω(m/T^{11/k}) and Ω(mΔ_V^{1/k}/T) for multipass algorithms and Ω(mΔ_E/T) for 1pass algorithms, which show that some of the dependencies on parameters in our upper bounds are nearly tight. Our techniques extend and generalize several different ideas previously developed for triangle counting in graphs, using appropriate innovations to handle the more complicated combinatorics of hypergraphs.more » « less

Chan, Timothy ; Fischer, Johannes ; Iacono, John ; Herman, Grzegorz (Ed.)We study fundamental directed graph (digraph) problems in the streaming model. An initial investigation by Chakrabarti, Ghosh, McGregor, and Vorotnikova [SODA'20] on streaming digraphs showed that while most of these problems are provably hard in general, some of them become tractable when restricted to the wellstudied class of tournament graphs where every pair of nodes shares exactly one directed edge. Thus, we focus on tournaments and improve the state of the art for multiple problems in terms of both upper and lower bounds. Our primary upper bound is a deterministic singlepass semistreaming algorithm (using Õ(n) space for nnode graphs, where Õ(.) hides polylog(n) factors) for decomposing a tournament into strongly connected components (SCC). It improves upon the previously bestknown algorithm by Baweja, Jia, and Woodruff [ITCS'22] in terms of both space and passes: for p ⩾ 1, they used (p+1) passes and Õ(n^{1+1/p}) space. We further extend our algorithm to digraphs that are close to tournaments and establish tight bounds demonstrating that the problem’s complexity grows smoothly with the "distance" from tournaments. Applying our SCCdecomposition framework, we obtain improved  and in some cases, optimal  tournament algorithms for s,treachability, strong connectivity, Hamiltonian paths and cycles, and feedback arc set. On the other hand, we prove lower bounds exhibiting that some wellstudied problems  such as (exact) feedback arc set and s,tdistance  remain hard (require Ω(n²) space) on tournaments. Moreover, we generalize the former problem’s lower bound to establish spaceapproximation tradeoffs: any singlepass (1± ε)approximation algorithm requires Ω(n/√{ε}) space. Finally, we settle the streaming complexities of two basic digraph problems studied by prior work: acyclicity testing of tournaments and sink finding in DAGs. As a whole, our collection of results contributes significantly to the growing literature on streaming digraphs.more » « less

Etessami, Kousha ; Feige, Uriel ; Puppis, Gabriele (Ed.)We study the time complexity of the discrete kcenter problem and related (exact) geometric set cover problems when k or the size of the cover is small. We obtain a plethora of new results:  We give the first subquadratic algorithm for rectilinear discrete 3center in 2D, running in Õ(n^{3/2}) time.  We prove a lower bound of Ω(n^{4/3δ}) for rectilinear discrete 3center in 4D, for any constant δ > 0, under a standard hypothesis about triangle detection in sparse graphs.  Given n points and n weighted axisaligned unit squares in 2D, we give the first subquadratic algorithm for finding a minimumweight cover of the points by 3 unit squares, running in Õ(n^{8/5}) time. We also prove a lower bound of Ω(n^{3/2δ}) for the same problem in 2D, under the wellknown APSP Hypothesis. For arbitrary axisaligned rectangles in 2D, our upper bound is Õ(n^{7/4}).  We prove a lower bound of Ω(n^{2δ}) for Euclidean discrete 2center in 13D, under the Hyperclique Hypothesis. This lower bound nearly matches the straightforward upper bound of Õ(n^ω), if the matrix multiplication exponent ω is equal to 2.  We similarly prove an Ω(n^{kδ}) lower bound for Euclidean discrete kcenter in O(k) dimensions for any constant k ≥ 3, under the Hyperclique Hypothesis. This lower bound again nearly matches known upper bounds if ω = 2.  We also prove an Ω(n^{2δ}) lower bound for the problem of finding 2 boxes to cover the largest number of points, given n points and n boxes in 12D . This matches the straightforward nearquadratic upper bound.more » « less

Megow, Nicole ; Smith, Adam (Ed.)We provide new approximation algorithms for the RedBlue Set Cover and Circuit Minimum Monotone Satisfying Assignment (MMSA) problems. Our algorithm for RedBlue Set Cover achieves Õ(m^{1/3})approximation improving on the Õ(m^{1/2})approximation due to Elkin and Peleg (where m is the number of sets). Our approximation algorithm for MMSA_t (for circuits of depth t) gives an Õ(N^{1δ}) approximation for δ = 1/3 2^{3⌈t/2⌉}, where N is the number of gates and variables. No nontrivial approximation algorithms for MMSA_t with t ≥ 4 were previously known. We complement these results with lower bounds for these problems: For RedBlue Set Cover, we provide a nearly approximation preserving reduction from Min kUnion that gives an Ω(m^{1/4  ε}) hardness under the DensevsRandom conjecture, while for MMSA we sketch a proof that an SDP relaxation strengthened by SheraliAdams has an integrality gap of N^{1ε} where ε → 0 as the circuit depth t → ∞.more » « less