Two applications of information complexity

ABSTRACT

We show the following new lower bounds in two concrete complexity models:<ol>

(1) In the two-party communication complexity model, we show that the tribes function on n inputs[6] has two-sided error randomized complexity Ω(n), while its nondeterminstic complexity and co-nondeterministic complexity are both Θ(√n). This separation between randomized and nondeterministic complexity is the best possible and it settles an open problem in Kushilevitz and Nisan[17], which was also posed by Beame and Lawry[5].

(2) In the Boolean decision tree model, we show that the recursive majority-of-three function on 3^h inputs has randomized complexity Ω((7/3)^h). The deterministic complexity of this function is Θ(3^h), and the nondeterministic complexity is Θ(2^h). Our lower bound on the randomized complexity is a substantial improvement over any lower bound for this problem that can be obtained via the techniques of Saks and Wigderson [23], Heiman and Wigderson[14], and Heiman, Newman, and Wigderson[13]. Recursive majority is an important function for which a class of natural algorithms known as directional algorithms does not achieve the best randomized decision tree upper bound.

</ol.These lower bounds are obtained using generalizations of information complexity, which quantifies the minimum amount of information that will have to be revealed about the inputs by every correct algorithm in a given model of computation.

REFERENCES

• 1: Farid Ablayev, Lower bounds for one-way probabilistic communication complexity and their application to space complexity, Theoretical Computer Science, v.157 n.2, p.139-159, May 5, 1996 [doi>10.1016/0304-3975(95)00157-3]
• 2: 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]
• 3: R. Bar-Yehuda, B. Chor, E. Kushilevitz, and A. Orlitsky. Privacy, additional information, and communication. IEEE Transactions on Information Theory, 39(6):1930--1943, 1993.
• 4: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar, An Information Statistics Approach to Data Stream and Communication Complexity, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.209-218, November 16-19, 2002
• 5: Paul Beame , Joan Lawry, Randomized versus nondeterministic communication complexity, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.188-199, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129732]
• 6: M. Ben-Or and N. Linial. Collective coin flipping. In S. Micali, editor, Randomness and Computation, pages 91--115. JAI Press, 1990.
• 7: M. Blum and R. Impagliazzo. General oracle and oracle classes. In Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, pages 118--126, 1987.
• 8: Harry Buhrman , Ronald de Wolf, Complexity measures and decision tree complexity: a survey, Theoretical Computer Science, v.288 n.1, p.21-43, 9 October 2002 [doi>10.1016/S0304-3975(01)00144-X]
• 9: A. Chakrabarti, Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.270, October 14-17, 2001
• 10: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 11: 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]
• 12: J. Hartmanis , L. A. Hemachandra, Complexity classes without machines: on complete languages for UP, Theoretical Computer Science, v.58 n.1-3, p.129-142, June 1988 [doi>10.1016/0304-3975(88)90022-9]
• 13: Rafi Heiman , Ilan Newman , Avi Wigderson, On read-once threshold formulae and their randomized decision tree complexity, Theoretical Computer Science, v.107 n.1, p.63-76, Jan. 4, 1993 [doi>10.1016/0304-3975(93)90254-Q]
• 14: R. Heiman and A. Wigderson. Randomized vs. deterministic decision tree complexity for read-once Boolean functions. Computational Complexity, 1:311--329, 1991.
• 15: J. Hromkovic , G. Schnitger, Nondeterministic communication with a limited number of advice bits, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.551-560, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238003]
• 16: M. Karchmer and A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3(2):255--265, 1990.
• 17: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 18: J. Lin. Divergence measures based on the Shannon entropy. IEEE Transactions on Information Theory, 37(1):145--151, 1991.
• 19: Ilan Newman, Private vs. common random bits in communication complexity, Information Processing Letters, v.39 n.2, p.67-71, July 31, 1991 [doi>10.1016/0020-0190(91)90157-D]
• 20: Noam Nisan, CREW PRAMs and decision trees, SIAM Journal on Computing, v.20 n.6, p.999-1007, Dec. 1991 [doi>10.1137/0220062]
• 21: Ran Raz , Avi Wigderson, Monotone circuits for matching require linear depth, Journal of the ACM (JACM), v.39 n.3, p.736-744, July 1992 [doi>10.1145/146637.146684]
• 22: Michael Saks , Xiaodong Sun, Space lower bounds for distance approximation in the data stream model, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509963]
• 23: M. Saks and A. Wigderson. Probabilistic Boolean decision trees and the complexity of evaluating game trees. In Proc. 27th IEEE Symposium on Foundations of Computer Science, pages 29--38, 1986.
• 24: Miklos Santha, On the Monte Carlo Boolean decision tree complexity of read-once formulae, Random Structures & Algorithms, v.6 n.1, p.75-87, Jan. 1995 [doi>10.1002/rsa.3240060108]
• 25: M. Snir. Lower bounds for probabilistic linear decision trees. Theoretical Computer Science, 38:69--82, 1985.
• 26: G. Tardos. Query complexity, or why is it difficult to separate NPA ∩ co-NPA from PA by a random oracle. Combinatorica, 9:385--392, 1990.
• 27: 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]
• 28: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Algorithms, Theory