Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read

ABSTRACT

A Boolean function of n bits is balanced if it takes the value 1 with probability 1⁄2. We exhibit a balanced Boolean function with a randomized evaluation procedure (with probability 0 of making a mistake) so that on uniformly random inputs, no input bit is read with probability more than Θ(n^-1/2√ log n). We construct a balanced monotone Boolean function and a randomized algorithm computing it for which each bit is read with probability Θ(n^-1⁄3 log n). We then show that for any randomized algorithm for evaluating a balanced Boolean function, when the input bits are uniformly random, there is some input bit that is read with probability at least Θ(n^-1𔊪). For balanced monotone Boolean functions, there is some input bit that is read with probability at least Θ(n^-1𔊫).

REFERENCES

• 1: Michael Ben-Or and Nathan Linial. Collective coin flipping. In S. Micali, editor, Randomness and Computation, pages 91--115, New York, 1989. Academic Press.
• 2: Itai Benjamini and Oded Schramm. Percolation beyond Zd, many questions and a few answers. Electron. Comm. Probab., 1(8):71--82, 1996.
• 3: M. Campanino and L. Russo. An upper bound on the critical percolation probability for the three-dimensional cubic lattice. Ann. Probab., 13(2):478--491, 1985.
• 4: T. S. Jayram , Ravi Kumar , D. Sivakumar, Two applications of information complexity, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780640]
• 5: Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on Boolean functions (extended abstract). In 29th Annual Symposium on Foundations of Computer Science, pages 68--80, 1988.
• 6: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 7: Radford M. Neal. Circularly-coupled Markov chain sampling. Technical Report 9910 (revised), Dept. of Statistics, University of Toronto, 2002.
• 8: Ryan O'Donnell, Mike Saks, Oded Schramm, and Rocco Servedio. Every decision tree has an influential variable, 2004. In preparation.
• 9: Ryan O'Donnell and Rocco Servedio. On decision trees, influences, and learning monotone decision trees. Technical Report CUCS-023-04, Columbia University, Dept. of Computer Science, 2004.
• 10: Alexander Polishchuk , Daniel A. Spielman, Nearly-linear size holographic proofs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.194-203, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195132]
• 11: James Gary Propp , David Bruce Wilson, How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph, Journal of Algorithms, v.27 n.2, p.170-217, May 1, 1998 [doi>10.1006/jagm.1997.0917 ]
• 12: M. Saks and A Wigderson. Probabilistic Boolean decision trees and the complexity of evaluating games. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pages 29--38, 1986.
• 13: Miklos Santha. On the Monte Carlo Boolean decision tree complexity of read-once formulae. In Structure in Complexity Theory Conference, pages 180--187, 1991.
• 14: Oded Schramm and Jeff Steif. Quantitative noise sensitivity and exceptional times for percolation, 2004. In preparation.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
boolean function, butterfly network, percolation, randomized decision tree