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
Thu Nov 6 11:24:08 PST 2014

Reminder: in ~1 hour!

On Wed, Nov 5, 2014 at 12:46 PM, Greg Bodwin <greg.bodwin at> wrote:

> 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: <>

More information about the theory-seminar mailing list