All reports by Author Giovanni Di Crescenzo:

__
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

Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano

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 ...
more >>>