Reminder: this is today.
--------------------------------------------
On 2022-07-18 13:13, Mykhaylo Tyomkyn wrote:
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.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz