Search Mailing List Archives
[theory-seminar] Theory Lunch 10/6: Josh Wang on Triangle Finding Algorithms
Greg Bodwin
greg.bodwin at gmail.com
Wed Nov 5 12:46:58 PST 2014
Hey all,
As usual, we'll have Theory Lunch this Thursday. Food at 12:15, talk at
12:30. Gates 4b wing lobby. Speaker details below.
Best,
Greg
---------------------------
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
three nodes.
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
slower algorithms.
Joint work with Virginia Vassilevska Williams, Ryan Williams, and Huacheng
Yu.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20141105/d6a7b63a/attachment.html>
More information about the theory-seminar
mailing list