Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > WORST-CASE:
Reports tagged with worst-case:
TR95-033 | 29th June 1995
Richard Beigel, David Eppstein

#### 3-Coloring in time O(1.3446^n): a no-MIS algorithm

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

TR07-097 | 8th October 2007
Miklos Ajtai, Cynthia Dwork

#### The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.

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

ISSN 1433-8092 | Imprint