Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR99-002 | 22nd January 1999
Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.

Approximating shortest lattice vectors is not harder than approximating closest lattice vectors.

We show that given oracle access to a subroutine which
returns approximate closest vectors in a lattice, one may find in
polynomial-time approximate shortest vectors in a lattice.
The level of approximation is maintained; that is, for any function
$f$, the following holds:
Suppose that the subroutine, on input a ... more >>>


TR99-001 | 4th January 1999
Detlef Sieling

The Complexity of Minimizing FBDDs

Revisions: 1

Free Binary Decision Diagrams (FBDDs) are a data structure
for the representation and manipulation of Boolean functions.
Efficient algorithms for most of the important operations are known if
only FBDDs respecting a fixed graph ordering are considered. However,
the size of such an FBDD may strongly depend on the chosen ... more >>>


TR98-078 | 1st December 1998
Vikraman Arvind, K.V. Subrahmanyam, N. V. Vinodchandran

The Query Complexity of Program Checking by Constant-Depth Circuits

In this paper we study program checking (in the
sense of Blum and Kannan) using constant-depth circuits as
checkers. Our focus is on the number of queries made by the
checker to the program being checked and we term this as the
query complexity of the checker for the given ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint