Article

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

Authors:

Itai Benjamini,

Oded Schramm,

David B. WilsonAuthors Info & Claims

STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

Pages 244 - 250

https://doi.org/10.1145/1060590.1060627

Published: 22 May 2005 Publication History

Get Access

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.

Google Scholar

[2]

Itai Benjamini and Oded Schramm. Percolation beyond Zd, many questions and a few answers. Electron. Comm. Probab., 1(8):71--82, 1996.

Crossref

Google Scholar

[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.

Crossref

Google Scholar

[4]

T. S. Jayram, Ravi Kumar, and D. Sivakumar. Two applications of information complexity. In Proceedings of the 35th ACM Symposium on the Theory of Computing, pages 673--682, 2003.

Digital Library

Google Scholar

[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.

Google Scholar

[6]

F. Thomson Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo, CA, 1992.

Digital Library

Google Scholar

[7]

Radford M. Neal. Circularly-coupled Markov chain sampling. Technical Report 9910 (revised), Dept. of Statistics, University of Toronto, 2002.

Google Scholar

[8]

Ryan O'Donnell, Mike Saks, Oded Schramm, and Rocco Servedio. Every decision tree has an influential variable, 2004. In preparation.

Google Scholar

[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.

Google Scholar

[10]

Alexander Polishchuk and Daniel A. Spielman. Nearly-linear size holographic proofs. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 194--203. ACM Press, 1994.

Digital Library

Google Scholar

[11]

James G. Propp and David B. 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, 27:170--217, 1998.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[14]

Oded Schramm and Jeff Steif. Quantitative noise sensitivity and exceptional times for percolation, 2004. In preparation.

Google Scholar

Cited By

View all

Zobolas JMonteiro PKuiper MFlobak Å(2022)Boolean function metrics can assist modelers to check and choose logical rulesJournal of Theoretical Biology10.1016/j.jtbi.2022.111025538(111025)Online publication date: Apr-2022
https://doi.org/10.1016/j.jtbi.2022.111025
Dewan VMuirhead S(2022)Upper bounds on the one-arm exponent for dependent percolation modelsProbability Theory and Related Fields10.1007/s00440-022-01176-3185:1-2(41-88)Online publication date: 22-Nov-2022
https://doi.org/10.1007/s00440-022-01176-3
Annaby MAyad HRushdi M(2018)On security of image ciphers based on logic circuits and chaotic permutationsMultimedia Tools and Applications10.1007/s11042-017-5439-677:16(20455-20476)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1007/s11042-017-5439-6
Show More Cited By

Index Terms

Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Boolean functions with two distinct Walsh coefficients

Are there other Boolean functions having two distinct Walsh coefficients except affine Boolean functions and maximal nonlinear (i.e. bent) Boolean functions__ __ This paper proves that all Boolean functions with exactly two distinct Walsh coefficients ...
On the Symmetric Negabent Boolean Functions
INDOCRYPT '09: Proceedings of the 10th International Conference on Cryptology in India: Progress in Cryptology

We study the negabent Boolean functions which are symmetric. The Boolean function which has equal absolute spectral values under the nega-Hadamard transform is called a negabent function. For a bent function, the absolute spectral values are the same ...
A Note on Semi-bent and Hyper-bent Boolean Functions
Information Security and Cryptology
Abstract
Semi-bent and hyper-bent funcitons as two classes of Boolean functions with low Walsh transform, are applied in cryptography and commnunications. This paper considers a new class of semi-bent quadratic Boolean function and a generalization of a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

May 2005

778 pages

ISBN:1581139608

DOI:10.1145/1060590

General Chair:
Hal Gabow
University of Colorado
,
Program Chair:
Ronald Fagin
IBM Almaden Research Center

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 May 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC05

Sponsor:

STOC05: Symposium on Theory of Computing

May 22 - 24, 2005

MD, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
482
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zobolas JMonteiro PKuiper MFlobak Å(2022)Boolean function metrics can assist modelers to check and choose logical rulesJournal of Theoretical Biology10.1016/j.jtbi.2022.111025538(111025)Online publication date: Apr-2022
https://doi.org/10.1016/j.jtbi.2022.111025
Dewan VMuirhead S(2022)Upper bounds on the one-arm exponent for dependent percolation modelsProbability Theory and Related Fields10.1007/s00440-022-01176-3185:1-2(41-88)Online publication date: 22-Nov-2022
https://doi.org/10.1007/s00440-022-01176-3
Annaby MAyad HRushdi M(2018)On security of image ciphers based on logic circuits and chaotic permutationsMultimedia Tools and Applications10.1007/s11042-017-5439-677:16(20455-20476)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1007/s11042-017-5439-6
Watson T(2015)Query Complexity in Errorless Hardness AmplificationComputational Complexity10.1007/s00037-015-0117-424:4(823-850)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s00037-015-0117-4
Ahlberg DBroman EGriffiths SMorris R(2014)Noise sensitivity in continuum percolationIsrael Journal of Mathematics10.1007/s11856-014-1038-y201:2(847-899)Online publication date: 7-Feb-2014
https://doi.org/10.1007/s11856-014-1038-y
Garban C(2011)Oded Schramm’s contributions to noise sensitivityThe Annals of Probability10.1214/10-AOP58239:5Online publication date: 1-Sep-2011
https://doi.org/10.1214/10-AOP582
Schramm OSteif J(2010)Quantitative noise sensitivity and exceptional times for percolationAnnals of Mathematics10.4007/annals.2010.171.619171:2(619-672)Online publication date: 25-Mar-2010
https://doi.org/10.4007/annals.2010.171.619
Hertel PPitassi T(2007)Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White PebblingProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science10.1109/FOCS.2007.25(137-149)Online publication date: 21-Oct-2007
https://dl.acm.org/doi/10.1109/FOCS.2007.25
O'Donnell RSaks MSchramm O(2005)Every decision tree has an in.uential variableProceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science10.1109/SFCS.2005.34(31-39)Online publication date: 23-Oct-2005
https://dl.acm.org/doi/10.1109/SFCS.2005.34

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Boolean functions with two distinct Walsh coefficients

On the Symmetric Negabent Boolean Functions

A Note on Semi-bent and Hyper-bent Boolean Functions