Boolean Functions: Influence, Threshold, and Noise

Here is the written version of my address at the 7ECM last July in Berlin.

Boolean functions, Influence, threshold, and Noise

Trying to follow an example of a 1925 lecture by Landau (mentioned in the lecture), the writing style is very much that of a lecture. It goes without saying that I will be very happy for corrections and suggestions of all kinds.

 

Advertisements
This entry was posted in Combinatorics, Computer Science and Optimization, Probability and tagged . Bookmark the permalink.

7 Responses to Boolean Functions: Influence, Threshold, and Noise

  1. gowers says:

    If the write-up is half as good as the lecture itself, then it will be a great read …

  2. Jon Awbrey says:

    This is very nice and will take me some study. I have been pursuing, off and on, the differential analysis of boolean functions, where influence is related to partial differentials. The main conceptual difficulty has been getting the right definition of the tangent functor. Here’s a link to more links:

    Survey of Differential Logic

  3. domotorp says:

    Simonovich and Sos should be Simonovits and T. S\’os.

    GK: Thanks! corrected!

  4. This looks very nice!
    One remark from reading just the first few pages so far: In Observation 1) on page 4, could it be that the argument should read: “Then $x$ must agree with $z$ on the last $n−k+1$ coordinates, giving $2^{k-1}$ possibilities for $x$, and $y$ must agree with $u$ on the first $k$ coordinates, giving $2^{n-k}$ possibilities for $y$,…”?

  5. Christian Elsholtz says:

    It would be good to include a direct reference to the Landau 1925 text (or the 23 problems): the bibliographic item Landau 1925b in the Corry-Schappacher paper mentions that it was reproduced in Landau’s collected works, (even though the referenced page numbers 297-289 of volume 8 seem unclear and should be checked).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s