In my last post, we saw that the problem of learning juntas, hard as it is over Boolean inputs, seems even worse over other alphabets. Coding theory happens to have a inexhaustible supply of such problems. Some of these are long-standing open problems, others are of a more recent vintage. More of these problems seem to crop up … Continue reading On the importance of the alphabet

Computational learning is full of problems that are deceptively simple to state but fiendishly hard to solve. Perhaps none more so than the problem of learning Juntas, posed by Avrim Blum and Pat Langley. Its the kind of problem which seems well suited for a polymath endeavor, Dick Lipton likes to say that you could … Continue reading Learning Juntas

Hastad's Switching Lemma is one of the gems of computational complexity. The switching lemma analyzes the effect of random restrictions on $latex AC^0$ circuits, which are constant depth circuits with AND, OR and NOT gates of unbounded fanin. It says that such restrictions tends to simplify  $latex AC^0$ circuits in surprising ways. An immediate consequence of the switching lemma is strong … Continue reading The Switching Lemma

The first question we'd like to answer is this: which is the monotone, balanced, transitive Boolean function which is least sensitive to bit-flips? We know that Majority is the worst possible with $latex NS( Maj) = \Theta(1/\sqrt{n})$. The new champion turns out to be the Tribes function first studied by Ben-Or and Linial. $latex Tribes_{s,w}$ … Continue reading When did Majority become the stablest? (Part 2)

The fireworks happening over at Ryan O'Donnell's blog reminded me of something that always puzzles me: Is Majority the Stablest? Or the Unstablest? Consider the class of all monotone, balanced Boolean functions $latex f:\{-1,1\}^n \rightarrow \{-1,1\}$. We define the noise sensitivity $latex NS(f)$ of a function $latex f$ as $latex NS(f) = P_{x,e}[f(x) \neq f( … Continue reading When did Majority become the stablest?