BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T090728Z
UID:Seminar-dept-1313@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20260127T130000
DTEND:20260127T140000
SUMMARY:School Seminar Series
DESCRIPTION:Vihan Shah: Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries\n\n We study the problem of estimating the size of the maximum matching in the sublinear-time setting. This problem has been extensively studied, with several known upper and lower bounds. A notable result by Behnezhad (FOCS 2021) established a 2-approximation in O~(n) time.\n\n\n\nHowever, all known upper and lower bounds are in the adaptive query model, where each query can depend on previous answers. In contrast, non-adaptive query models—where the distribution over all queries must be fixed in advance—are widely studied in property testing, often revealing fundamental gaps between adaptive and non-adaptive complexities. This raises the natural question: is adaptivity also necessary for approximating the maximum matching size in sublinear time? This motivates the goal of achieving a constant or even a polylogarithmic approximation using O~(n) non-adaptive adjacency list queries, similar to what was done by Behnezhad using adaptive queries.\n\n\n\nWe show that this is not possible by proving that any randomized non-adaptive algorithm achieving an n^{1/3 - gamma}-approximation, for any constant gamma > 0, with probability at least 2/3, must make Omega(n^{1 + eps}) adjacency list queries, for some constant eps > 0 depending on gamma. This result highlights the necessity of adaptivity in achieving strong approximations. However, non-trivial upper bounds are still achievable: we present a simple randomized algorithm that achieves an n^{1/2}-approximation in O(n \log n) queries.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1313
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR