Pith. sign in

REVIEW

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

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv math/0410282 v1 pith:EVWA6GXW submitted 2004-10-12 math.PR cs.CC

classification math.PRcs.CC
keywords balancedbooleanprobabilityinputfunctionreadthetabits
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original 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 Theta(n^{-1/2} sqrt{log n}). We give a balanced monotone Boolean function for which the corresponding probability is Theta(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 Theta(n^{-1/2}). For balanced monotone Boolean functions, there is some input bit that is read with probability at least Theta(n^{-1/3}).

Discussion (0). Continue with ORCID to comment.

Pith tools