We consider worst case time bounds for NP-complete problems including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a common generalization of these problems, called symbol-system satisfiability or, briefly, SSS [R. Floyd & R. Beigel, The Language of Machines]. 3-SAT is equivalent to (2,3)-SSS while the other problems ... more >>>

We describe a public-key cryptosystem with worst-case/average case equivalence. The cryptosystem has an amortized plaintext to ciphertext expansion of $O(n)$, relies on the hardness of the $\tilde O(n^2)$-unique shortest vector problem for lattices, and requires a public key of size at most $O(n^4)$ bits. The new cryptosystem generalizes a conceptually ... more >>>