Oded Goldreich

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

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

Oded Goldreich, Liav Teichner

We initiate a study of super-perfect zero-knowledge proof systems.

Loosely speaking, these are proof systems for which the interaction can be perfectly simulated in strict probabilistic polynomial-time.

In contrast, the standard definition of perfect zero-knowledge only requires that the interaction can be perfectly simulated

by a strict probabilistic polynomial-time that ...
more >>>