2015 · 66 citations · 62 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsParallel AlgorithmsAlgorithm AnalysisComputational AlgebraComputational ComplexityGraph AlgorithmsMatrix ComputationShortest Path AlgorithmsAll-pairs Shortest PathsComputational Complexity Of Graph AlgorithmsMatrix MultiplicationParallel Matrix MultiplicationParallel Matrix-vector MultiplicationShortest PathsSubgraph MiningUpper Bounds
In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the congested clique model. Specifically, we adapt parallel matrix multiplication implementations to the congested clique, obtaining an O(n1-2/ω) round matrix multiplication algorithm, where ω < 2.3728639 is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include: triangle and 4-cycle counting in O(n0.158) rounds, improving upon the O(n1/3) triangle counting algorithm of Dolev et al. [DISC 2012], a (1 + o(1))-approximation of all-pairs shortest paths in O(n0.158) rounds, improving upon the ~O (n1/2)-round (2 + o(1))-approximation algorithm of Nanongkai [STOC 2014], and computing the girth in O(n0.158) rounds, which is the first non-trivial solution in this model. In addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles.
62
Gaussian elimination is not optimal
Volker Strassen · Numerische Mathematik · 1969 · 2.5K citations
Noga Alon, Raphael Yuster, Uri Zwick · Journal of the ACM · 1995 · 1K citations · Full text
Powers of tensors and fast matrix multiplication
François Le Gall · 2014 · 873 citations
Finding and counting given length cycles
Noga Alon, Raphael Yuster, Uri Zwick · Algorithmica · 1997 · 613 citations
Finding a Minimum Circuit in a Graph
Alon Itai, Michael Rodeh · SIAM Journal on Computing · 1978 · 397 citations