Minimum communication cost for zero knowledge proofs of three colorability Goldreich et al.'s proof that three colorability has zero knowledge proofs uses bit commitment for an entire coloring of the graph in each round [1].  If a graph has $n$ vertices and $e$ edges, a secure hash has $b$ bits, and we seek error probability $p$, the total communication cost is

$$O(ben \log(1/p))$$

over $O(1)$ rounds.  Using a gradually revealed Merkle tree, the total communication can be reduced to $O(be \log n \log (1/p))$ at the cost of increasing the number of rounds to $O(\log n)$.

Is it possible to do better than this, either in terms of total communication or number of rounds?


http://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf


Edit: Thanks to Ricky Demer for pointing out the missing factor of $e$.
So here is the right paper for my purposes:

Joe Kilian, "A note on efficient zero-knowledge proofs and arguments." http://people.csail.mit.edu/vinodv/6892-Fall2013/efficientargs.pdf

To get the strongest result, we need to accept zero knowledge arguments rather than proofs (computationally bounded prover); these are what I am interested in but did not know the terminology.

Assuming sufficient cryptographic assumptions, the paper gives zero knowledge arguments with total communication $O(b \log^c n \log (1/p))$ for $c = O(1)$.

This result is tightened to $O(1)$ rounds by Ishai et al., "On Efficient Zero-Knowledge PCPs", http://www.cs.virginia.edu/~mohammad/files/papers/13%20ZKPCPs.pdf.