Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-120 | 24th September 2012 22:28

Proof vs. Truth in Computational Complexity

RSS-Feed




Revision #1
Authors: Boaz Barak
Accepted on: 24th September 2012 22:28
Downloads: 3704
Keywords: 


Abstract:

In this survey, I discuss the general question of what evidence can we use to predict the answer for open questions in computational complexity, as well as the concrete evidence currently known for two conjectures: Khot's Unique Games Conjecture and Feige's Random 3SAT Hypothesis.



Changes to previous version:

Corrected a typo in the definition of the small set expansion problem.


Paper:

TR12-120 | 24th September 2012 22:06

Proof vs. Truth in Computational Complexity





TR12-120
Authors: Boaz Barak
Publication: 24th September 2012 22:07
Downloads: 3487
Keywords: 


Abstract:

In this survey, I discuss the general question of what evidence can we use to predict the answer for open questions in computational complexity, as well as the concrete evidence currently known for two conjectures: Khot's Unique Games Conjecture and Feige's Random 3SAT Hypothesis.



ISSN 1433-8092 | Imprint