[theory-seminar] Theory Lunch 10/6: Josh Wang on Triangle Finding Algorithms

[Greg Bodwin]

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>