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-019 | 6th March 1996
C.P. Schnorr

Security of 2^t-Root Identification and Signatures


TR96-018 | 23rd February 1996
Oded Goldreich, Johan HÃ¥stad

On the Message Complexity of Interactive Proof Systems

Revisions: 2

We investigate the computational complexity of languages
which have interactive proof systems of bounded message complexity.
In particular, we show that
(1) If $L$ has an interactive proof in which the total
communication is bounded by $c(n)$ bits
then $L$ can be recognized a probabilitic machine
in time ... more >>>


TR96-017 | 19th February 1996
Christoph Meinel, Stephan Waack

The ``Log Rank'' Conjecture for Modular Communication Complexity


The ``log rank'' conjecture consists in the question how exact
the deterministic communication complexity of a problem can be
determinied in terms of algebraic invarants of the communication
matrix of this problem. In the following, we answer this question
in the context of modular communication complexity. ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint