« Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
November 09, 2022, 11:00 AM - 12:15 PM
Location:
Online Event
Bundit Laekhanukit, Shanghai University of Finance and Economics
In a recent breakthrough [STOC'21], Lin proves that there is no fpt-algorithm that can approximate the clique problem with any constant ratio unless FPT= W[1]. This is subsequently improved by Karthik C. S. and Khot [CCC'22] to the inapproximability of ratio k^{o(1)}. We present a much-simplified proof of this result. At the core of our proof is a novel encoding of k-element subsets inspired by network coding together with a natural extension of Sidon sets.
This is joint work with Yijia Chen (SJTU), Yi Feng (SUFE) and Yanlin Liu (Fudan).
Zoom Meeting: https://rutgers.zoom.us/j/94994409309?pwd=S0FvMFMrbW5RTlhyRTBWRGV2MGtOUT09
Meeting ID: 949 9440 9309
Password: 725976