Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR96-054 | 2nd November 1996 00:00

#### The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

TR96-054
Authors: Oded Goldreich
Publication: 5th November 1996 16:20
Keywords:

Abstract:

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 this problem has a (perfect) zero-knowledge
interactive proof system.

### Comment(s):

Comment #1 to TR96-054 | 2nd February 1998 13:59

#### The Graph Clustering Problem has a Perfect Zero-Knowledge Proof Comment on: TR96-054.

Comment #1
Authors: Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano
Accepted on: 2nd February 1998 13:59
Keywords:

Abstract:

We have posted, as TR98-006, an improvement over TR96-054.
Whereas TR96-054 considers the parametrized
(by sequence of integers) problem,
the new posting refers to the non-parametrized version
where these integers are part of the input.

ISSN 1433-8092 | Imprint