Richard Beigel, David Eppstein

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 >>>

Miklos Ajtai, Cynthia Dwork

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 >>>