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 Yi Feng (SUFE), Bundit Laekhanukit (SUFE), and Yanlin Liu (Fudan).

Time

2022-06-07  13:30 - 14:30   

Speaker

Yijia Chen,  SJTU

Room

Tencent meeting ID: 853-8759-9058; PW: 123456