ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > ZERO-KNOWLEDGE INTERACTIVE PROOFS:
Reports tagged with Zero-Knowledge Interactive Proofs:
TR96-054 | 2nd November 1996
Oded Goldreich

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

Comments: 1

The Graph Clustering Problem is parameterized by a sequence
of positive integers, $m_1,...,m_t$.
The input is a sequence of $\sum_{i=1}^{t}m_i$ graphs,
and the question is whether the equivalence classes
under the graph isomorphism relation have sizes which match
the sequence of parameters.
In this note
we show that ... more >>>


TR98-006 | 27th January 1998
Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

The input to the {\em Graph Clustering Problem}\/
consists of a sequence of integers $m_1,...,m_t$
and a sequence of $\sum_{i=1}^{t}m_i$ graphs.
The question is whether the equivalence classes,
under the graph isomorphism relation,
of the input graphs have sizes which match the input sequence of integers.
In this note we ... more >>>




ISSN 1433-8092 | Imprint