Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-181 | 30th December 2021 17:37

The KW Games as a Teaser

RSS-Feed




TR21-181
Authors: Oded Goldreich
Publication: 30th December 2021 17:37
Downloads: 1043
Keywords: 


Abstract:

This is a purely pedagogical text.
We advocate using KW-games as a teaser (or ``riddle'') for a complexity theoretic course.
In particular, stating the KW-game for a familiar NP-complete problem such as 3-Colorability and asking to prove that it requires more than polylogarithmic communication poses a seemingly tractable question that requires no background.
The fact that this is actually a formidable question puts much of complexity theory in the right perspective.
Indeed, complexity theory contains numerous extremely appealing problems that require little background (beyond basic comfort with the notion of computation) and yet are formidable.



ISSN 1433-8092 | Imprint