Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- 19 June 2016
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
- p. 375-388
- https://doi.org/10.1145/2897518.2897653
Abstract
No abstract availableKeywords
Funding Information
- Alfred P. Sloan Foundation
- United States - Israel Binational Science Foundation (BSF:2012338)
- National Science Foundation (CCF-1417238,CCF-1514339, and CCF-1212372)
- Carlsbergfondet (CF14-0617)
This publication has 38 references indexed in Scilit:
- Improving Exhaustive Search Implies Superpolynomial Lower BoundsSIAM Journal on Computing, 2013
- A new algorithm for optimal 2-constraint satisfaction and its implicationsTheoretical Computer Science, 2005
- An improved exponential-time algorithm for k -SATJournal of the ACM, 2005
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problemsJournal of Computer and System Sciences, 2003
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- Bounded-width polynomial-size branching programs recognize exactly those languages in NC1Journal of Computer and System Sciences, 1989
- A Turing machine time hierarchyTheoretical Computer Science, 1983
- A faster algorithm computing string edit distancesJournal of Computer and System Sciences, 1980
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970