@ARTICLE{Barak12,
  AUTHOR =       {Boaz Barak},
  TITLE =        {Truth vs. Proof in Computational Complexity},
  JOURNAL =      {Bulletin of the European Association for Theoretical Computer Science},
  YEAR =         {2012},
  number =       {108},
  month =        {October},
  note =         {Appeared in Logic in Computer Science column. Also posted in Windows on theory blog},
   url_paper = {https://www.boazbarak.org/Papers/truth-proof.pdf},
   url_blog = {http://windowsontheory.org/2012/07/31/truth-vs-proof-the-unique-games-conjecture-and-feiges-hypothesis/},
}

{"_id":"tGYLj7dZp8SXDtyZc","bibbaseid":"barak-truthvsproofincomputationalcomplexity-2012","downloads":7,"creationDate":"2016-05-29T21:28:44.731Z","title":"Truth vs. Proof in Computational Complexity","author_short":["Barak, B."],"year":2012,"bibtype":"article","biburl":"www.boazbarak.org/boaz.bib","bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Boaz"],"propositions":[],"lastnames":["Barak"],"suffixes":[]}],"title":"Truth vs. Proof in Computational Complexity","journal":"Bulletin of the European Association for Theoretical Computer Science","year":"2012","number":"108","month":"October","note":"Appeared in Logic in Computer Science column. Also posted in Windows on theory blog","url_paper":"https://www.boazbarak.org/Papers/truth-proof.pdf","url_blog":"http://windowsontheory.org/2012/07/31/truth-vs-proof-the-unique-games-conjecture-and-feiges-hypothesis/","bibtex":"@ARTICLE{Barak12,\n AUTHOR = {Boaz Barak},\n TITLE = {Truth vs. Proof in Computational Complexity},\n JOURNAL = {Bulletin of the European Association for Theoretical Computer Science},\n YEAR = {2012},\n number = {108},\n month = {October},\n note = {Appeared in Logic in Computer Science column. Also posted in Windows on theory blog},\n url_paper = {https://www.boazbarak.org/Papers/truth-proof.pdf},\n url_blog = {http://windowsontheory.org/2012/07/31/truth-vs-proof-the-unique-games-conjecture-and-feiges-hypothesis/},\n}\n\n\n","author_short":["Barak, B."],"key":"Barak12","id":"Barak12","bibbaseid":"barak-truthvsproofincomputationalcomplexity-2012","role":"author","urls":{" paper":"https://www.boazbarak.org/Papers/truth-proof.pdf"," blog":"http://windowsontheory.org/2012/07/31/truth-vs-proof-the-unique-games-conjecture-and-feiges-hypothesis/"},"metadata":{"authorlinks":{"barak, b":"https://www.boazbarak.org/papers/"}},"downloads":7},"search_terms":["truth","proof","computational","complexity","barak"],"keywords":[],"authorIDs":["574b9fd5d2f1ef9e28000281","5de6e3bbeab4b7de0100001c","5de733d397054edf0100015a","5de7425d6a9377de01000083","5de794a6d9b46bde010000bf","5de823104e3c5af3010000f0","5de85d1c8ff138de010000a7","5de8a4192c5eb2df0100017e","5de90c9cd5dfa2e001000175","5de91395d5dfa2e001000235","5de97326768c31df010000d7","5de9abe05b51bcde01000078","5dea5020ddb5e6df01000067","5dea68984f43c9de01000029","5dea9833a71b4bdf01000174","5deab4c703c11ade01000202","5deae851ecff01ef010000ea","5deb29b328b3ebde01000111","5debbb12ca1cdddf01000025","5debbc54ca1cdddf0100004c","5dec504ee16431f2010000a7","5dec903c12c53edf010000cd","5decc8580ec6b9df010000bd","5ded376b9d5885de010000e1","5ded3c399d5885de0100011f","5dee1081584fb4df010000d1","5dee597feaaee4df01000275","5dee84aefc4c19df01000150","5dee8eb4fc4c19df0100024a","5deeb8300ddb85de010000b3","5deedecf66e59ade010000f4","5deefc90dca291de0100012c","5def118dc5ae39f2010000de","5def3508e83f7dde010000fc","5def5ff9fe2024de01000080","5deff42c14db5cdf0100011d","5df00656e128adde01000058","5df00b5ee128adde0100009f","5df039ccaa8415de01000009","5df059fbe4ce32df0100003e","5df0981cf651f5df010000a4","5df0acb68367c8de01000024","5df13f52630a9ee0010000b7","5df154d3d177badf01000051","5df16b38d177badf010001c5","5df172ff57cfb4de01000041","5df17fe957cfb4de010000d1","5df1ab0580f800de0100003f","5df1bd9080f800de01000100","5df1cf461070c8ef010000a6","5df1d5001070c8ef010000f7","5df2572163aac8df0100008f","5df265a163aac8df0100019a","5df2b38b0f18f1df01000109","5df2b6090f18f1df0100013f","5df320b43b310cde010000ba","5df3668ed617e5de01000186","5df37dba23fb6fdf01000159","5df3de06ccbb4fde0100006b","5df4935c5ad889f0010000aa","5df4ab9aa50a84df01000078","5df4d999fc47dbde01000029","5df4e0effc47dbde01000082","5df5233eea1457de0100010b","5df53f4efd245cde01000131","5df551a1ff5784de0100008d","5df580c84734a4de01000021","5df58d9f428212df01000031","5df59cbea0eab8de01000024","5df5a9f1a0eab8de010000d4","5df5b316a0eab8de0100013b","5df5b99d64d1d0df0100001f","5df5d4a7f65dd9de0100000b","5df5dd29f65dd9de01000065","5df5e378f65dd9de01000097","5df60334a37a40df010000f0","5df61b4c2b34d0de010000a5","5df63b8b38e915de010000d9","5df644badf30fcdf01000009","5df650d6df30fcdf010000c8","5df65f88df30fcdf010001bd","5df6728b797ba9de010000e6","5df6927372bbd4df0100010c","5df6aa6131a37ade01000110","5df6ad3731a37ade0100013d","5df75cf0182af9de01000226","5df76c45952c76df01000116","5df77092952c76df01000149","5df7b59392a8e4df0100004b","5df7efc7b9bb17df0100006b","5df82ca4dc1981de01000082","5df87a00db7d9ddf01000026","5df87d38db7d9ddf01000055","5df8e8b2277e45de01000025","5df909d12e8c31df010000ca","5df992edc4ada8de01000011","5df99f90c4ada8de010000c0","5df9b258a344e2ef01000052","5dfa5dc47d1403df010000a5","5dfa77c72a0346de0100004e","5dfb6f1ac2820bdf0100001c","5dfb9619749b8bde01000094","5dfbb3a0f6f0aede010000c1","5dfbcb8e4705b7de0100007f","5dfbf89f4d4fb9de010001a7","5dfcfc6cea1680de01000037","5dfd1b66ece35ede01000053","5dfd3e05575d0fde0100008f","5dfec3ae4f2cf6de01000030","5dfee6295dd8e7df01000055","5dff1f4b7769f4de0100008b","5e00c0d57a90b3de0100007a","5e012bcc2e225bde01000057","5e0265cb2862b0de0100004c","5e02b39119da8edf0100002f","5e02df2d410ebcdf0100007d","5e0310edf2d70dde01000084","5e034683fe9387de01000049","5e03a9be745356de010000f2","5e03d9436d2066de0100008d","5e03ed71ee776fdf01000046","5e041be3c51eb3de01000001","5e049f3810c665de010000c8","5e04f489fff612df01000119","5e054e8d1965a8de01000103","5e0591ffd36daddf01000038","5e0606ace95bcdde01000070","5e0616978e1565f20100000a","5e067e1c78d770df0100031e","5e06b2283cb7b3df0100008b","5e06c376a0810cde01000026","5e072b36865432df01000086","5e08767bffbbabdf0100007b","5e0902c379e131f301000099","5e0918a8361f52de0100006e","5e098cdc83a3f3de01000061","5e09e6f4503781de010000a4","5e0a2e6d01dcffde0100006b","5e0aaa8d610902df010000ca","5e0b079fa129adde01000003","5e0b0f0aa129adde01000038","5e0bc38a94c532f3010000c9","5e0bdab68db71cdf0100005a","5e0c8629464605de010000ab","5e0d7f3da04810df01000077","5e0dcd85552b25df01000057","5e0dfd9a45d2fdde01000107","5e0e2a282b8028de01000095","5e0e537bac7d11df01000002","5e0f3a442c4a31df01000052","5e0f5ecc44d21ddf010000a4","5e0fa09766a55ede01000199","5e1023402ef76bdf0100006f","5e10e88545c12cde01000085","5e11a4702af340df01000025","5e120ff5440202de0100000c","5e12435ec196d3de0100012c","5e129778551229df010000b5","5e13598a697554de0100015a","5e136564f16095df01000086","5e139037a212e1de01000126","5e13d492dd177ade01000025","5e1468040467fede0100009a","5e1479c10467fede010001d3","5e14a85b830852de01000193","5e154e7eedfb1ede01000122","5e15642a1e2528de01000042","5e159910e8bfcff201000040","5e160771f67f7dde0100008e","5e1677da0ba191df0100005d","5e16a184da4561de010000a8","5e17dee04ba003df01000139","5e18e8228fcbc2df010000d2","5e18fb288fcbc2df010001c7","5e1912d4a7672ede01000120","5e1ba1f261cb16df0100002d","5e1bd2f7ce7a9bde010000ca","5e1ca7c97723aadf01000053","5e1cd74babed9bde01000059","5e1d38b66b18c4df010000bf","5e1ddfe24986afdf01000178","5e1e4d9b2e41a7de0100009e","5e1eafa2bedb58de01000157","5e1f0ef73cc57cde01000061","5e1f33d407379ade01000127","5e1f4cc29ddd0fde01000134","5e202ea902c04cde010000fa","5e20796480350bdf0100007a","5e20ad0c5c2065de0100000f","5e21c9aaaf8ac1df01000044","5e2275c5c39817df01000022","5e227912c39817df01000044","5e228bbfa9b15cde0100000c","5e23950ded52aedf01000077","5e24a68e1a6264de01000049","5e24c671981ceddf01000050","5e2574c7f58a5cde010000fb","5e25f8e12368a7de0100004c","5e25faff2368a7de0100008b","5e26315924c8a6de01000060","5e2747e218178ede01000045","5e274e9218178ede010000c6","5e27523f18178ede010000ed","5e27f14e4d75d8de01000034","5e2858b7c4828cde0100019b","5e28a9e588416fde010001b7","5e28b05288416fde01000240","5e2900d041639df301000088","5e29cb54888177df0100000a","5e29d340888177df010000a0","5e29dc57888177df01000140","5e2a03ac2d6a3dde01000007","5e2a15ea2d6a3dde01000129","5e2a42962d8494f20100005a","5e2a7e8c881468de0100004d","5e2b32b827ed83df01000115","5e2cc42b972628f201000017","5e2cdc52972628f201000105","5e2d372104d333de0100001f","5e2d52955e7586df01000014","5e2d85a1556d50df010000d1","5e2de02e133023de01000030","5e2eac07b84405df010000cb","5e2ee99f9033bede01000177","5e2f35a578a7cedf010000a5","5e2f41c778a7cedf010001b7","5e2fb12da21e47de010000fd","5e2fb35ba21e47de01000125","5e30534257a222df010000dd","5e30a894c99510de01000109","5e30ba472a1e4bde01000070","5e30ccc02a1e4bde010001ba","5e3204217c8d24df010001b7","5e327f443957e3df01000058","5e32983ce17accde0100003f","5e32c395466076df0100011c","5e32ec9fc1389bde01000061","5e330b46200286df01000078","5e33e6ddd41331de01000007","5e344daf0c807ede01000174","5e34cc0262bc74de01000046","5e3626d31727e7df010000ba","5e36a6b77b975dde0100000c","5e36ef18b26a0fde010000f5","5e372302646a98de010000e7","5e374bfd4cbab2df0100020d","5e383eafca2b4bde01000197","5e388635030bcadf0100002e","5e3889c3030bcadf01000077","5e38d7df81a46ade01000005","5e38ff81dc5b8ade0100007e","5e390caedc5b8ade0100011a","5e3964b8346d7cde01000007","5e396c60346d7cde010000bd","5e397541346d7cde01000169","5e3985aad14579de01000093","5e399020d14579de010001a5","5e39d5353687dddf01000008","5e39e07c3687dddf010000de","5e3a624bb291e7df0100000d","5e3aa7004518d5df010000c7","5e3ac84ef2a00cdf01000172","5e3b027255f0f2df0100013e","5e3b2262ba2e16df0100017c","5e3b40a8255dcade010001e3","5e3b690659b923df0100007b","5e3c6c4467788ede010000e0","5e3c96b4f99721de0100002b","5e3ca4bcf99721de01000101","5e3cb35e948886de0100001d","5e3ccc9a5cd237de01000008","5e3d2b85c405ecde01000095","5e3e38be546544df010000d1","5e3e5576018e1dde010000bb","5e3e600cac2d49de01000039","5e3e830d666d79df01000095","5e3ee25086a596de0100012c","5e3f0cf3e7f957de010000a1","5e3f22447da304de0100004b","5e4048ae668183de010000e0","5e40e6adfd6934df01000092","5e4124fbb54187de01000107","5e412721b54187de0100014d","5e4164e6a59dc8df010001c8","5e4193228491fadf01000129","5e41a0ad8491fadf01000232","5e41b7fd0b4861de0100018f","5e41ea14a9454ade0100010e","5e4223e870cecede0100010c","5e42540f82b0c2de01000043","5e4294dd5ea111df0100012b","5e432d698957d0de01000023","5e4335178957d0de01000097","5e434a7ea37866de01000020","5e43afbda3f5a4de010000c6","5e43bf6644c4f9df01000085","5e43c83b44c4f9df010001b3","5e44345ce5a34dde0100013c","5e445b65df3c2af30100019f","5e44cbb27759a7df01000125","5e45081903c52dde01000157","5e452310501a51de0100017d","5e456f3449667cde01000154","5e45b7570920e8de01000044","5e45bad70920e8de010000a0","5e45e33fad0603df0100015e","5e461d4ab57382df010000ec","5e474d9bd8f94bde010000bc","5e47bc336c5c7ede01000090","5e48827986dc17de01000091","5e4897396ac344de01000069","5e4915e627cbfcdf01000099","5e499144552c77df0100004a","5e49c9cdb63120f20100004f","5e4a1e5dd2dbc8de0100003b","5e4a9201b70966df010000df","5e4af25b41072bdf01000163","5e4b3563a44fbbde0100003c","5e4b9fe02d0ef5de0100013e","5e4be8fa8f0677df010000e1","5e4c8177f2c6ddde0100019e","5e4cba7a0cc7d3de01000003","5e4cec563e28aede01000130","5e4d18467d0ec8de010000ba","5e4d63f308a8e5de01000014","5e4d86e5d2986bde010000df","5e4d8f77d2986bde0100019e","5e4e208ad116fbde0100014d","5e4e604c24a828df01000005","5e4e67ca24a828df01000089","5e4e83849b7bbade0100006d","5e4e9cd764b624de0100003f","5e5025aa8c3a2cde01000021","5e504350c708b1de0100004d","5e50c297e3d144df01000075","5e51785af29c90df01000021","5e518072f29c90df01000066","5e5220c1fe135dde01000017","5e5253e4bf8729de010000c1","5e5291c81ce297df01000038","5e53291112ed54df010000a3","5e53349d12ed54df0100011b","5e533e5f53de8dde0100003f","5e540ab2e81566de01000116","5e54246580c0b0de010000f8","5e5439957a758fde01000096","5e5484c77f0f44de01000135","5e554b46ca58a8df0100021e","5e55ead4c2c8a2df0100009d","5e566dc6df3460df01000098","5e56d0c796127bde010001d9","5e57143c429006de01000043","5e576f0d16d3d2f301000096","5e57736616d3d2f3010000d5","5e5792a9cef9b7de01000109","5e57a902041daade0100010a","5e57e30ee391bbde01000152","5e57e572e391bbde0100018b","5e58367c1f3fc8de010000d9","5e587f841d5966df0100001f","5e5889c6c8b5dede01000024","5e591eaf9bb6d2df01000179","5e5952f5f5822adf0100013b","5e596a6056d60ade0100012b","5e5979b18049fcde01000009","5e5985138049fcde0100009d","5e599da2ad6c7fde010000c8","5e59b8bf103b4fde0100005a","5e59d1f0ab416cde0100003e","5e59ebdf6ef27ddf0100001d","5e5ad4a8d85d5dde01000078","5e5af64b038583de010000ce","5e5d57ccad47bcde0100006c","5e5d76530b73f6de010000b2","5e5d8dc25726ecdf0100003f","5e5dcd11c64f0ede0100007e","5e5de22e863279df0100002f","5e5e5ed05f9e7bee01000168","5e5e711714f49fde01000078","5e5e9134c0a53dde0100013b","5e5e971bc0a53dde010001b8","5e5f5a4ffff7e8de01000075","5e5fb31919c3fade01000190","5e5fff1113e3aede0100007d","5e6003be13e3aede010000bc","5e603ba2182590df010000c0","5e6044d6182590df01000120","5e604c364a1c7edf01000023","5e60ea12839e59df0100011a","5e611e8a1cc34ede0100017d","5e61659b417d19de0100006a","5e633c2a716092de010000b9","5e6937b46964dedf01000123","7hQBbyvc4fK73YzkC","7m5xuBBdq3HNpsYBS","8KidKSuoYxAvWixPR","8YzsYqbJF9g8GSWsT","Dq2FXdMNaeLLxiP7j","DtMngyLPRPMKp7AXj","Dz5gWwZkxYC7pd6g6","FANtuzAcR83AqXXQT","Gg44hSn9Lzz324QKo","J6t9f3fvcaujBNhq4","J6ypHpCNWcLYa5H6z","K2Qcb8xo5BKjzwv2P","MgAwQnpNE3FPRELfk","PaZ2d2HymhmTWX9Wr","QKD6xKEPuS5N2L4Jj","QgPrMPMzqDpnvpcnx","R9GotQua7iEG4qBuv","RT4SCKYkdoTHQxySL","SceJPncEhMktWHwPL","TwMYcL5ZMQaRSK9fb","WBQSZcd9ujE8DWttN","XHCxQ3PqJDWqmNRus","XyMYq53YDY2vwEP9q","YRspA8F3Hucpp6jqh","Yh2rievbri6ZaLkan","Zf7pGfK8yyw3hzNZH","a9Ccyy8dzeCzKkBc8","as8qc2L6FLdT2EbGD","bnAzhebKSJMc34Xvu","bntKAZ5rqi7jMgcE2","c65R6eY2AkQuJMe7Z","cbh8JqHqm5p2MfeLk","csm2gdD5fCd4nbyKn","dFrEstcmMMJBJFcjM","dLmwbCjWCJgxLAtTH","dWXkj4uEsPPF3bbYo","dYM6zodFS9HuYX2bg","ercwZRH6tbSnoMPBG","gAefPWHik62DixCe6","hvinEvrC8xTitzE5a","hx4He5x3Ya3RDsJQv","m3rP8QXj3pn3cqsjT","mph2gBHGQhNFRYioy","nh2iFEQNJrFN9QThn","nrCajhMLt4LdC5XsH","oGJAhiqiAKSbhEXss","sEFC5NAEKAbkG8oc2","sTADyMqtjjbJe6bLk","uWFBiG7AscG3PcuYG","uZcqDiKqjnCqaJ5ph","wCjtR5GbDRHRPyuzr","yah7Nue9TgfMvFgii","zomdSvGE7F9pwxqKv"],"dataSources":["ZdZkvHBZGR7Mt6sXE","jomRn3LFHawZsjFia","sNDcqxpX5cBQ5Pu7G","763eChmCTEH5onHpy","rRM8G92fpDDvXxQen"]}