Seminar Details
Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
- Start Date: November 9, 2022
- Event Start Time: 11:00 AM
- Event End Time: 12:15 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Bundit Laekhanukit - Shanghai University of Finance and Economics
- Event Location: Online Event
- Event Additional Info: <p>Zoom Meeting: <a href="https://rutgers.zoom.us/j/94994409309?pwd=S0FvMFMrbW5RTlhyRTBWRGV2MGtOUT09" target="_blank">https://rutgers.zoom.us/j/94994409309?pwd=S0FvMFMrbW5RTlhyRTBWRGV2MGtOUT09</a></p> <p>Meeting ID: 949 9440 9309</p> <p>Password: 725976</p>
- Presentation Type: Stand Alone Presentation
- Abstract:
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).