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

TR96-007 | 29th January 1996
Miklos Ajtai

Generating Hard Instances of Lattice Problems

Comments: 1

We give a random class of n dimensional lattices so that, if
there is a probabilistic polynomial time algorithm which finds a short
vector in a random lattice with a probability of at least 1/2
then there is also a probabilistic polynomial time algorithm which
solves the following three ... more >>>


TR96-006 | 24th January 1996
Bernd Borchert, Antoni Lozano

Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept

This note connects two topics of Complexity Theory: The
topic of succinct circuit representations initiated by
Galperin and Wigderson and the topic of leaf languages
initiated by Bovet, Crescenzi, and Silvestri. It will be
shown for any language that its succinct version is
more >>>


TR96-005 | 9th January 1996
Hans-Joerg Burtschick, Heribert Vollmer

Lindstroem Quantifiers and Leaf Language Definability

Revisions: 1


We show that examinations of the expressive power of logical formulae
enriched by Lindstroem quantifiers over ordered finite structures
have a well-studied complexity-theoretic counterpart: the leaf
language approach to define complexity classes. Model classes of
formulae with Lindstroem quantifiers are nothing else than leaf
language definable sets. Along the ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint