Dear all,
This week we will have a noon lecture on Thursday 21 July, given by Jakub Tětek. Please find the talk details below.
Best regards, Misha Tyomkyn.
----------------------------------------
Jakub Tětek Basic Algorithms Research Copenhagen and University of Copenhagen July 21, 2022, 12:20 in S6
Abstract There is a simple O(n^3/eps^2 T) time algorithm for 1+-eps-approximate triangle counting where T is the number of triangles in the graph and n the number of vertices. At the same time, one may count triangles exactly using fast matrix multiplication in time O(n^\omega). Is it possible to get a negative dependency on the number of triangles T while retaining the state-of-the-art n^\omega dependency on n? We answer this question positively by providing an algorithm which runs in time O(n^\omega/T^(\omega - 2)) poly(n^o(1)/eps). This is optimal in the sense that as long as the exponent of T is independent of n, T, it cannot be improved while retaining the dependency on n. Our algorithm improves upon the state of the art when T >> 1 and T << n. We also consider approximate triangle counting in sparse graphs.
The paper is a (shared) best student paper at ICALP 2022.
-----------------------------------------