Backurs, Indyk connect strong exponential time hypothesis to edit distance; other CS time/ space hierarchy/ continuum news

hi all. recently Backurs/ Indyk just got a paper accepted into STOC 2015 connecting the Strong Exponential Time Hypothesis (“SETH”) with tight bounds on computing edit distance. the latter has many applications across CS and also plays a big role in bioinformatics and computational biology wrt DNA sequences where it relates to natural alterations, ie more specifically “biologically occurring genetic processes”—eg even occuring in our own bodies… and surely cant get more “applied” than that!

there is some buzz/ excitement on this result as this is regarded as something of a breakthrough. it reminds me of the concept of “the microcosm reflects the macrocosm and vice versa” aka/ in short, “as above, so below”. a polynomial time algorithm speed (“the small”) seems to have major implications for speed of NP complete problems wrt exponential time (“the large”) and vice versa.[a]

⭐ ➡ and moreover/ further, near-dramatic connection/ exhibition/ manifestation/ confirmation of an apparent deep/ recurring principle/ theme/ “design pattern” in CS, interconnection/ interdependency of upper and lower bounds. at times upper and lower bounds seems like the yin and yang of TCS… 💡 😮 ❤

oh, but alas, not exactly; some fine print, its not quite as strong as one might hope. SETH implies P≠NP but based on current knowledge, SETH false could have no implication on P vs NP. a near miss? maybe this line of study might have even more direct implications on proving P≠NP with more study? (ie proving tight lower bounds on edit distance implying P≠NP?)

anyway it gives me an excuse to unleash a big pile of links on one of my favorite subjects, the CS “time/space hierarchy/ continuum” (doesnt it just sound so exotic, like something out of star trek or the matrix?) 😎 😀

there have also been neat recent results on L vs P connected to intersection nonemptiness of DFAs by Wehar. worked on this problem myself years ago empirically and had suspicions it might be connected to deep complexity class separations and its really great to see this confirmed. Wehar is active on & has even chatted some about his paper & other topics, a big highlight for me. hi MW![b] 🙂

one of my favorite topics in CS & P vs NP is the transition point which think likely will play a big role in any P vs NP proof, but alas research on the subject seems to have dropped off in recent years, although there is still a lot of interest and mass amounts of papers written on the subject. Moshe Vardi recently posted a comprehensive youtube lecture that showed up on reddit. it seems a nearly striking/ gaping omission to me that wikipedia has no entry on the subject, which connects/ crosscuts deep CS to physics. any takers?[c]

natural proofs by razborov/ rudich (2007 Nevanlinna prize) has a big role in P vs NP study and there has been some newer ideas on it from Chow leading to some glimmers of reexamination lately. natural proofs is considered a so-far nearly insurmountable barrier against P vs NP proofs and its great to see some deeper analysis/ rethinking on the subject.[d]

a. Backurs, Indyk, SETH vs edit distance/ P vs NP
b. L vs P
c. transition
d. natural proofs
e. etc

One thought on “Backurs, Indyk connect strong exponential time hypothesis to edit distance; other CS time/ space hierarchy/ continuum news

  1. Pingback: Terence Tao magic breakthrough again with EDP, Erdos Discrepancy Problem, topnotch links | Turing Machine

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s