Information Theory versus Complexity Theory: Another Test Case
Ivan Damgard, Oded Goldreich, Avi Wigderson.
Abstract: A few cases are known where the computational analogue of some basic information theoretical results is much harder to prove or even not known to hold. A notable example is Yao's XOR Lemma. Actually, even Direct Sum Conjectures can be viewed as analogues of trivial probabilistic facts. Here we present yet another example of this phenumena. Unlike the examples mentioned above, here we dont know whether even a weak version of the computational analogue holds.
Keywords: Protocols, hashing functions, zero-knowledge, interactive proofs, argument systems.
comment: received May 9th, 1996. Written in September 1995
contact author: oded@wisdom.weizmann.ac.il
Fetch PostScript file of the full paper.