44d SHLOMO HOORY.NATHAN LINIAL.AND AVI WIGDERSON 1.1.Three motivating problems 1.1.1.Hardness results for linear transformations.The P vs.NP problem is ar- guably the most important open problem in theoretical computer science.Despite its great significance and despite intensive research efforts,very little progress has been made.But interesting aspects of computational complexity can be investi- gated in other,more restricted contexts.For example,we may consider evaluating polynomials over a field using only the field's arithmetic,or even evaluating linear transformations using only addition and multiplication by scalars from the field Valiant [Val76]considered the following natural problem: Problem 1.1.Let A be an nxn matrix over the field!F.What is the least number of gates in a circuit that computes the linear transformation xAr?Each gate is specified by two field elements a and b.Such a gate receives two inputs z and y and outputs ax +by. Aside from its profound theoretical importance,certain instances of this question have far-reaching technological significance.Consider the matrix ar.s=w"s(n-1> r.s >0),where w is a primitive n-th root of unity.The transformation Ax is the Discrete Fourier Transform,which is fundamental to many modern technologies involving signal processing,machine learning,etc.As observed by Cooley and Tukey CT65,there is a circuit realizing this linear transformation (the so-called Fast Fourier Transform(FFT))with only O(nlogn)gates.Therefore the least number of gates in such a circuit is between O(n logn)and n(which are required just to input the vector z).This may seem like a small gap in our knowledge, but it is rather significant.The technological implications of a Very Fast Fourier Transform,i.e.an O(n)-sized circuit that computes the transform (should one exist),are hard to overestimate.On the other hand,it would be a great theoretical breakthrough to establish a matching lower bound of (nlogn),or even rule out the existence of such a circuit with only O(n)gates. For every field F,it is fairly easy to show that for most n x n matrices A,every circuit realizing A must have (n2/log n)gates.This is based on a counting argu- ment that compares the number of circuits with a given number of gates and the number of n x n matrices over the field.As is often the case in computational com- plexity,despite this abundance of computationally hard functions,we are unable to exhibit any specific,explicit linear transformation A that requires asymptot- ically more then O(n)gates.In an attempt to solve this problem,Valiant [Val76] conjectured that super regular transformations are "hard"in this sense. Definition 1.2(Super Regular Matrix).A matrix A is super regular if every square sub-matrix of A has full rank. Valiant considered the graph layout of a circuit which realizes the linear trans- formation corresponding to a super regular matrix.His main observation was that this graph must be a super concentrator: Definition 1.3(Super Concentrator).Let G=(V,E)be a graph and let I and O be two subsets of V with n vertices,each called the input and output sets respectively.We say that G is a super concentrator if for every k and every SI and T CO with S=T=k,there exist k vertex disjoint paths in G from S to T IThis problem is interesting for finite as well as for infinite fields.444 SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON 1.1. Three motivating problems. 1.1.1. Hardness results for linear transformations. The P vs. NP problem is ar￾guably the most important open problem in theoretical computer science. Despite its great significance and despite intensive research efforts, very little progress has been made. But interesting aspects of computational complexity can be investi￾gated in other, more restricted contexts. For example, we may consider evaluating polynomials over a field using only the field’s arithmetic, or even evaluating linear transformations using only addition and multiplication by scalars from the field. Valiant [Val76] considered the following natural problem: Problem 1.1. Let A be an n×n matrix over the field1 F. What is the least number of gates in a circuit that computes the linear transformation x
→ Ax? Each gate is specified by two field elements a and b. Such a gate receives two inputs x and y and outputs ax + by. Aside from its profound theoretical importance, certain instances of this question have far-reaching technological significance. Consider the matrix ar,s = ωrs (n−1 ≥ r, s ≥ 0), where ω is a primitive n-th root of unity. The transformation x
→ Ax is the Discrete Fourier Transform, which is fundamental to many modern technologies involving signal processing, machine learning, etc. As observed by Cooley and Tukey [CT65], there is a circuit realizing this linear transformation (the so-called Fast Fourier Transform (FFT)) with only O(n log n) gates. Therefore the least number of gates in such a circuit is between O(n log n) and n (which are required just to input the vector x). This may seem like a small gap in our knowledge, but it is rather significant. The technological implications of a Very Fast Fourier Transform, i.e. an O(n)-sized circuit that computes the transform (should one exist), are hard to overestimate. On the other hand, it would be a great theoretical breakthrough to establish a matching lower bound of Ω(n log n), or even rule out the existence of such a circuit with only O(n) gates. For every field F, it is fairly easy to show that for most n × n matrices A, every circuit realizing A must have Ω(n2/ log n) gates. This is based on a counting argu￾ment that compares the number of circuits with a given number of gates and the number of n×n matrices over the field. As is often the case in computational com￾plexity, despite this abundance of computationally hard functions, we are unable to exhibit any specific, explicit linear transformation A that requires asymptot￾ically more then O(n) gates. In an attempt to solve this problem, Valiant [Val76] conjectured that super regular transformations are “hard” in this sense. Definition 1.2 (Super Regular Matrix). A matrix A is super regular if every square sub-matrix of A has full rank. Valiant considered the graph layout of a circuit which realizes the linear trans￾formation corresponding to a super regular matrix. His main observation was that this graph must be a super concentrator : Definition 1.3 (Super Concentrator). Let G = (V,E) be a graph and let I and O be two subsets of V with n vertices, each called the input and output sets respectively. We say that G is a super concentrator if for every k and every S ⊆ I and T ⊆ O with |S| = |T| = k, there exist k vertex disjoint paths in G from S to T. 1This problem is interesting for finite as well as for infinite fields