Title :
Geometric arguments yield better bounds for threshold circuits and distributed computing
Author :
Krause, Matthias
Author_Institution :
FB Inf., Dortmund Univ., Germany
fDate :
30 Jun-3 Jul 1991
Abstract :
The computational power of two-party probabilistic communication protocols is investigated. This model generalizes the concepts of nondeterministic and conondeterministic communication protocols in a natural way. Applications of the technique are presented, and some open problems are stated
Keywords :
computational complexity; protocols; threshold logic; bounds; computational power; conondeterministic communication protocols; distributed computing; geometric arguments; nondeterministic protocols; threshold circuits; two-party probabilistic communication protocols; Binary decision diagrams; Circuits; Complexity theory; Computer networks; Distributed computing; Eigenvalues and eigenfunctions; Game theory; Iron; Protocols; Random sequences;
Conference_Titel :
Structure in Complexity Theory Conference, 1991., Proceedings of the Sixth Annual
Conference_Location :
Chicago, IL
Print_ISBN :
0-8186-2255-5
DOI :
10.1109/SCT.1991.160275
