ECCC-Report TR96-054https://eccc.weizmann.ac.il/report/1996/054Comments and Revisions published for TR96-054en-usMon, 02 Feb 1998 13:59:13 +0200
Comment 1
| The Graph Clustering Problem has a Perfect Zero-Knowledge Proof Comment on: TR96-054. |
Alfredo De Santis,
Giovanni Di Crescenzo,
Oded Goldreich,
Giuseppe Persiano
https://eccc.weizmann.ac.il/report/1996/054#comment1
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.
Mon, 02 Feb 1998 13:59:13 +0200https://eccc.weizmann.ac.il/report/1996/054#comment1
Paper TR96-054
| The Graph Clustering Problem has a Perfect Zero-Knowledge Proof |
Oded Goldreich
https://eccc.weizmann.ac.il/report/1996/054
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.
Tue, 05 Nov 1996 16:20:14 +0200https://eccc.weizmann.ac.il/report/1996/054