- Backurs, Indyk connect Strong Exponential Time Hypothesis (SETH) to edit distance; other CS time/ space hierarchy/ continuum news https://vzn1.wordpress.com/2015/07/10/backurs-indyk-connect-strong-exponential-time-hypothesis-to-edit-distance-other-cs-time-space-hiearchy-continuum-news/ 3 comments compsci
Linked pages
- Longstanding problem put to rest | MIT News | Massachusetts Institute of Technology http://newsoffice.mit.edu/2015/algorithm-genome-best-possible-0610 300 comments
- For 40 years, computer scientists looked for a solution that doesn’t exist - The Boston Globe http://www.bostonglobe.com/ideas/2015/08/10/computer-scientists-have-looked-for-solution-that-doesn-exist/txo0qnrnbkrclfupmavifk/story.html 160 comments
- Quanta Magazine https://www.quantamagazine.org/20150929-edit-distance-computational-complexity/ 40 comments
- How not to prove that P is not equal to NP | Gowers's Weblog http://gowers.wordpress.com/2013/10/03/how-not-to-prove-that-p-is-not-equal-to-np/ 18 comments
- We Believe A Lot, But Can Prove Little | Gödel's Lost Letter and P=NP http://rjlipton.wordpress.com/2011/01/19/we-believe-a-lot-but-can-prove-little/ 11 comments
- 40-year-old algorithm proven the best possible http://phys.org/news/2015-06-year-old-algorithm-proven.html 5 comments
- Video from Theoretical Foundations of Applied SAT Solving http://www.birs.ca/events/2014/5-day-workshops/14w5101/videos/watch/201401231116-vardi.html 4 comments
- Razborov and Rudich’s natural proofs argument | Gowers's Weblog http://gowers.wordpress.com/2013/10/07/razborov-and-rudichs-natural-proofs-argument/ 0 comments
- ds.algorithms - Polynomial-time algorithms with huge exponent/constant - Theoretical Computer Science Stack Exchange http://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant 0 comments
- Who’s Afraid of Natural Proofs? | Gödel's Lost Letter and P=NP http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs/ 0 comments
- Natural proof - Wikipedia https://en.wikipedia.org/wiki/Natural_proof 0 comments
- Gödel Prize - Wikipedia https://en.wikipedia.org/wiki/G%C3%B6del_Prize 0 comments