Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

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

Greg Bodwin greg.bodwin at
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.



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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list