Search Mailing List Archives
[theory-seminar] Theory Lunch 10/6: Josh Wang on Triangle Finding Algorithms
greg.bodwin at gmail.com
Wed Nov 5 12:46:58 PST 2014
As usual, we'll have Theory Lunch this Thursday. Food at 12:15, talk at
12:30. Gates 4b wing lobby. Speaker details below.
We present new algorithms for finding induced four-node subgraphs in a
given graph, which run in time roughly that of detecting a clique on
The best known algorithms for triangle finding in an n-node graph take
O(n^w) time, where w < 2.373 is the matrix multiplication exponent. We
give a general randomized technique for finding any induced four-node
subgraph, except for the clique or independent set on 4 nodes, in
Õ(n^w) time with high probability. The algorithm can be derandomized
in some cases.
For sparse graphs with m edges, the best known triangle finding
algorithm runs in O(m^(2w/(w+1))) <= O(m^1.41) time. We give a
randomized Õ(m^(2w/(w+1))) time algorithm for finding any induced
four-node subgraph other than C_4, K_4 and their complements. Some
cases can be derandomized. For C_4 or its complement, we get slightly
Joint work with Virginia Vassilevska Williams, Ryan Williams, and Huacheng
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar