Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jonathan Katz:

TR13-013 | 18th January 2013
Daniel Apon, Jonathan Katz, Alex Malozemoff

One-Round Multi-Party Communication Complexity of Distinguishing Sums

Revisions: 1

We consider an instance of the following problem: Parties $P_1,..., P_k$ each receive an input $x_i$, and a coordinator (distinct from each of these parties) wishes to compute $f(x_1,..., x_k)$ for some predicate $f$. We are interested in one-round protocols where each party sends a single message to the coordinator; ... more >>>

TR07-065 | 13th July 2007
Jonathan Katz

Which Languages Have 4-Round Zero-Knowledge Proofs?

We show that if a language $L$ has a 4-round, black-box, computational zero-knowledge proof system with negligible soundness error, then $\bar L \in MA$. Assuming the polynomial hierarchy does not collapse, this means, in particular, that $NP$-complete languages do not have 4-round zero-knowledge proofs (at least with respect to black-box ... more >>>

TR06-028 | 21st February 2006
Jonathan Katz, Chiu-Yuen Koo

On Expected Constant-Round Protocols for Byzantine Agreement

In a seminal paper, Feldman and Micali (STOC '88) show an n-party Byzantine agreement protocol tolerating t < n/3 malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., $t < n/2$), and relying only on the ... more >>>

ISSN 1433-8092 | Imprint