Randomized versus nondeterministic communication complexity

ABSTRACT

Our main result is the demonstration of a Boolean function f with nondeterministic and co-nondeterministic complexities O(log n) and &egr;-error randomized complexity &OHgr;(log2 n), for 0 ≤ &egr; < 1/2. This is the first separation of this kind for a decision problem.

REFERENCES

• AUY83: Alfred V. Aho , Jeffrey D. Ullman , Mihalis Yannakakis, On notions of information transfer in VLSI circuits, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.133-139, December 1983 [doi>10.1145/800061.808742]
• BI87: M. Bhm and R. impagliazzo. Generic oracles and oracle classes. In 28th Annual Symposium on Foundations o/ Computer Science, pages 118-126, Los Angeles, CA, October 1987. IEEE.
• DF89: D. Dolev and T. Feder. Multiparty communication complexity. In 30th Annual Symposium on Foundations of Computer Science, pages 428-433, Research Triangle Park, NC, October 1989. IEEE. Corrected version.
• Für87: M. Furer, The power of randomness for communication complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.178-181, January 1987, New York, New York, United States [doi>10.1145/28395.28415]
• GH89: M. Goldmann and J. H~stad. A lower bound for monotone clique using a communication game. Manuscript, 1989.
• HH87: Juris Hartmanis , Lane A. Hemachandra, One-Way Functions, Robustness, and the Non-Isomorphism of NP-Complete Sets, Cornell University, Ithaca, NY, 1987
• HR88: Bernd Halstenberg , Rudiger Reischuk, On different modes of communication, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.162-172, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62226]
• KW88: Mauricio Karchmer , Avi Wigderson, Monotone circuits for connectivity require super-logarithmic depth, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.539-550, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62265]
• Law92: Joan Lawry. PhD thesis, University of Washington, 1992.
• LNNW91: László Lovász , Moni Naor , Ilan Newman , Avi Wigderson, Search problems in the decision tree model (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.576-585, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185422]
• MS82: Kurt Mehlhorn , Erik M. Schmidt, Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.330-337, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802208]
• Raz88: A.A. Razborov. Applications of matrix methods to the theory of lower bounds in computational complexity. Manuscript, 1988.
• RW89: Ran Raz and Avi Wigderson. Probabilistic communication complexity of Boolean relations, in 30th Annual Symposium on Foundations of Computer Science, pages 562-567, Research Triangle Park, NC, October 1989. IEEE. Full version.
• RW90: R. Raz , A. Wigderson, Monotone circuits for matching require linear depth, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.287-292, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100253]
• Sni85: M. Snir. Lower bounds on probabilistic linear decision trees. Theoretical Computer Science, 38:69-82, 1985.
• SW86: M. Saks and A. Wigderson. Probabilistic Boolean decision trees and the complexity of evaluating games trees. in 27th Annual Symposium on Foundations of Computer Science, pages 29- 38, Toronto, Ontario, October 1986. IEEE.
• Tar88: G. Tardos. Query complexity, or why is it difficult to separate NpA#coNPA by a random oracle A? Manuscript, 1988.
• Yao79: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
• Yao81: Andrew C. Yao, The entropic limitations on VLSI computations(Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.308-311, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802483]
• Yao83: A.C. Ya#. Lower bounds by probabilistic arguments. In 24th Annual Symposium on Foundations of Computer Science, pages 420-428, Tucson, AZ, November 1983. IEEE.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Decision problems

General Terms:
Performance, Theory