A new conjecture on hardness of 2-CSP’s with implications to hardness of densest \(k\)-subgraph and other problems. (English) Zbl 07918359
Kalai, Yael Tauman (ed.), 14th innovations in theoretical computer science conference, ITCS 2023, January 10–13, 2023, MIT, Cambridge, Massachusetts, USA. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 251, Article 38, 23 p. (2023).
MSC:
68Qxx