Ami Paz Technion

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 multipli-cation 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 algorith-mics, 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, im-proving 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 Õ(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