EXPANDER GRAPHS AND THEIR APPLICATIONS 445 It is a simple exercise to show that indeed the underlying graph of any circuit for a super regular matrix is a super concentrator (with inputs and outputs retaining their meaning in both).Valiant conjectured that any super concentrator must have>n edges.That would have implied that any circuit which computes a super regular matrix must have>n gates.However,Valiant himself disproved the conjecture and presented super concentrators with O(n)edges.As you may have guessed,this is where expanders come into the picture. We note that this construction can actually be used to give a super regular ma- trix that has a linear sized circuit,which seems to put this approach to rest.This is not quite so,and Valiant's ideas were later realized,as follows:If we consider circuits with more than two inputs per gate but where the circuit's depth is re- stricted,then superlinear lower bounds for the number of edges in depth-limited super concentrators were proven [DDPW83].Subsequently the desired superlinear lower bounds for computing the associated linear transformations in bounded-depth circuit model were derived Lok01.RS03 Even though this approach did not yield strong lower bounds on circuit sizes, these attempts have brought forward the importance of sparse super concentrators in network theory and other areas.Valiant's idea has eventually had a major impact on the field. We now skip to a totally different problem. 1.1.2.Construction of good error correcting codes.One of the most fundamental problems in communication is noise.Suppose that Alice has a message of k bits which she would like to deliver to Bob over some(noisy)communication channel. The problem is that noise in the channel may corrupt the message so that Bob receives a message that differs from the one sent by Alice. In his ground-breaking paper "A Mathematical Theory of Communication" [Sha48,Claude Shannon laid the foundations for Information Theory and the mathematical theory of communication.The problem of communicating over a noisy channel(which in the form below was suggested by Hamming H50])occupies a central part of this theory. Problem 1.4 (communication over noisy channel).Alice and Bob communicate over a noisy channel.A fraction p of the bits sent through the channel may be altered.What is the smallest number of bits that Alice can send,assuming she wants to communicate an arbitrary k-bit message,so that Bob should be able to unambiguously recover the original message? To solve this problem,Shannon suggested creating a dictionary (or code)CC {0,l}n of size IC]=2 *and using a bijective mapping(“an encoding”）p:{0,l}k→ C.To send a message x e {0,1,Alice transmits the n-bit encoded message ()EC.It is assumed that Bob receives a string y{0,1)"that is a corrupted version of the message actually sent (r)EC.Bob finds the codeword 2EC that is closest to y (the metric used is the Hamming distance:d(u,v)is the number of coordinates i where ui vi).He concludes that the message actually sent was (z).If the distance between every two words in C is greater than 2pn,it is guaranteed that indeed z=(r),and Bob correctly infers the message sent by Alice. The problem of communicating over a noisy channel is thus reduced to the problem of finding a good dictionary:namely,a set C of n-bit strings of largestEXPANDER GRAPHS AND THEIR APPLICATIONS 445 It is a simple exercise to show that indeed the underlying graph of any circuit for a super regular matrix is a super concentrator (with inputs and outputs retaining their meaning in both). Valiant conjectured that any super concentrator must have  n edges. That would have implied that any circuit which computes a super regular matrix must have  n gates. However, Valiant himself disproved the conjecture and presented super concentrators with O(n) edges. As you may have guessed, this is where expanders come into the picture. We note that this construction can actually be used to give a super regular ma￾trix that has a linear sized circuit, which seems to put this approach to rest. This is not quite so, and Valiant’s ideas were later realized, as follows: If we consider circuits with more than two inputs per gate but where the circuit’s depth is re￾stricted, then superlinear lower bounds for the number of edges in depth-limited super concentrators were proven [DDPW83]. Subsequently the desired superlinear lower bounds for computing the associated linear transformations in bounded-depth circuit model were derived [Lok01, RS03]. Even though this approach did not yield strong lower bounds on circuit sizes, these attempts have brought forward the importance of sparse super concentrators in network theory and other areas. Valiant’s idea has eventually had a major impact on the field. We now skip to a totally different problem. 1.1.2. Construction of good error correcting codes. One of the most fundamental problems in communication is noise. Suppose that Alice has a message of k bits which she would like to deliver to Bob over some (noisy) communication channel. The problem is that noise in the channel may corrupt the message so that Bob receives a message that differs from the one sent by Alice. In his ground-breaking paper “A Mathematical Theory of Communication” [Sha48], Claude Shannon laid the foundations for Information Theory and the mathematical theory of communication. The problem of communicating over a noisy channel (which in the form below was suggested by Hamming [H50]) occupies a central part of this theory. Problem 1.4 (communication over noisy channel). Alice and Bob communicate over a noisy channel. A fraction p of the bits sent through the channel may be altered. What is the smallest number of bits that Alice can send, assuming she wants to communicate an arbitrary k-bit message, so that Bob should be able to unambiguously recover the original message? To solve this problem, Shannon suggested creating a dictionary (or code) C ⊆ {0, 1}n of size |C| = 2k and using a bijective mapping (“an encoding”) ϕ : {0, 1}k → C. To send a message x ∈ {0, 1}k, Alice transmits the n-bit encoded message ϕ(x) ∈ C. It is assumed that Bob receives a string y ∈ {0, 1}n that is a corrupted version of the message actually sent ϕ(x) ∈ C. Bob finds the codeword z ∈ C that is closest to y (the metric used is the Hamming distance: dH (u, v) is the number of coordinates i where ui = vi). He concludes that the message actually sent was ϕ−1(z). If the distance between every two words in C is greater than 2pn, it is guaranteed that indeed z = ϕ(x), and Bob correctly infers the message sent by Alice. The problem of communicating over a noisy channel is thus reduced to the problem of finding a good dictionary: namely, a set C of n-bit strings of largest