Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR96-054 | 2nd November 1996 00:00

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

RSS-Feed




TR96-054
Authors: Oded Goldreich
Publication: 5th November 1996 16:20
Downloads: 2083
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
Downloads: 1751
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