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

TR02-063 | 3rd December 2002
Oded Goldreich

Zero-Knowledge twenty years after its invention

Zero-knowledge proofs are proofs that are both convincing and yet
yield nothing beyond the validity of the assertion being proven.
Since their introduction about twenty years ago,
zero-knowledge proofs have attracted a lot of attention
and have, in turn, contributed to the development of other
areas of cryptography and complexity ... more >>>


TR02-062 | 19th November 2002
Andrew Chi-Chih Yao

Classical Physics and the Church-Turing Thesis

Would physical laws permit the construction of computing machines
that are capable of solving some problems much faster than the
standard computational model? Recent evidence suggests that this
might be the case in the quantum world. But the question is of
great interest even in the realm of classical physics. ... more >>>


TR02-061 | 14th November 2002
Miklos Ajtai

A conjectured 0-1 law about the polynomial time computable properties of random lattices, I.

A measure $\mu_{n}$ on $n$-dimensional lattices with
determinant $1$ was introduced about fifty years ago to prove the
existence of lattices which contain points from certain sets. $\mu_{n}$
is the unique probability measure on lattices with determinant $1$ which
is invariant under linear transformations with determinant $1$, where a
more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint