We end this book with a concise list of open questions which are grouped by theme.

Randomized algorithms

13.1.1 Best randomized algorithm for Iterated Majority

It may look surprising (owing to the simple iterative structure of the Iterated Majority function introduced in Example 1.5), but the following problem is to our knowledge not settled.

Open Problem 13.1Find the randomized algorithm with smallest possible revealment for the Iterated Majority function fk on n = 3k bits. Even the order of magnitude of the decay to 0 (i.e., the exponent) is not known although there are some known bounds.

13.1.2 Best randomized algorithms for critical percolation

Open Problem 13.2

(a) Find algorithms for crossing events in percolation on the triangular lattice that examine on average at most n7/4−∈ sites for some ∈>0.

(b) Show that any algorithm examines on average at least n6/4+∈ sites for some ∈ > 0. (This would strengthen the lower bound obtained in Section 8.4 in Chapter 8).

13.1.3 Randomized algorithm and spectrum One way to obtain better bounds on the noise sensitivity of a Boolean function through the randomized algorithm approach (e.g., the percolation crossing events fn) is to find the algorithms with the smallest possible revealments. Another possible direction is to address the following problem.

Open Problem 13.3Prove a sharper version of Theorem 8.2 from (SS10).

13.1.4 Randomized algorithms and pivotal points

In (PSSW07), the authors introduce a seemingly very efficient randomized algorithm: one starts at some random initial site (using a well-chosen initial distribution) and then at each step, one picks the site that has the largest probability to be pivotal conditioned on what has been revealed so far. See (PSSW07). Their numerical simulations suggest that this randomized algorithm is more efficient than the one we used in Chapter 8 using an interface. Yet, nothing is rigorously known.