Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-198 | 14th December 2016 20:52

Towards a Proof of the 2-to-1 Games Conjecture?

RSS-Feed




TR16-198
Authors: Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
Publication: 14th December 2016 20:53
Downloads: 3789
Keywords: 


Abstract:

We propose a combinatorial hypothesis regarding a subspace vs. subspace agreement test, and prove that if correct it leads to a proof of the 2-to-1 Games Conjecture, albeit with imperfect completeness.



ISSN 1433-8092 | Imprint