Expanders from symmetric codes

ABSTRACT

(MATH) A set S in the vector space FF_pⁿ is "good" if it satisfies the following (almost) equivalent conditions:

• S is an expanding generating set of Abelian group FF_pⁿ.
• S are the rows of a generating matrix for a linear distance error-correcting code in FF_pⁿ.
• All (nontrivial) Fourier coefficients of S are bounded by some &egr; ξ 1 (i.e. the set S is &egr;-biased).

.A good set S must have at least cn vectors (with cρ1). We study conditions under which S is the orbit of only constant number of vectors, under the action of a finite group G on the coordinates. Such succinctly described sets yield very symmetric codes, and "amplifies" small constant-degree Cayley expanders to exponentially larger ones [19, 2].For the regular action (the coordinates are named by the elements of the group G), we develop representation theoretic conditions on the group G which guarantee the existence (in fact, abundance) of such few expanding orbits. The condition is a (nearly tight) upper bound on the distribution of dimensions of the irreducible representations of G, and is the main technical contribution of this paper. We further show a class of groups for which this condition is implied by the expansion properties of the group G itself! Combining these, we can iterate the amplification process above, and give (near-constant degree) Cayley expanders which are built from Abelian components.For other natural actions, such as of the affine group on a finite field, we give the first explicit construction of such few expanding orbits. In particular, we can completely derandomize the probabilistic construction of expanding generators in [2].

REFERENCES

• 1: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 2: A. Lubotzky, Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.630, October 14-17, 2001
• 3: N. Alon and V. Milman. λ1, isoperimetric inequalities for graphs and superconcentrators. J. Combinatorial Theory Ser. B, 38:73--88, 1985.
• 4: M. Aschbacher. Finite Group Theory. Cambridge University Press, Cambridge, 2000.
• 5: T. Brown and J. Buhler. A density version of a geometric ramsey theorem. J. Combin. Theory Ser. A, 32:20--34, 1982.
• 6: L. Carter and M. Wegman. Universal classes of hash functions. J. Computer and System Sciences, 18:143--154, 1979.
• 7: P. de la Harpe, A. G. Robertson, and A. Valette. On the spectrum of the sum of generators for a finitely generated group. Israel J. of (MATH)., 81:65--96, 1993.
• 8: Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
• 9: O. Gabber and Z. Galil. Explicit construction of linear sized superconcentrators. J. Comp. and Sys. Sci, 22:407--420, 1981.
• 10: I. Isaacs. Character Theory of Finite Groups. Academic Press, New York, 1976.
• 11: I. Isaacs. Generalizations of taketa's theorem on the solvability of M-groups. Proc. Amer. (MATH). Soc., 91:192--194, 1984.
• 12: A. Lubotzky. Discrete Groups, Expanding Graphs and Invariant Measures. Birkhauser Verlag, Basel, 1994.
• 13: A. Lubotzky, R. Philips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8:261--277, 1988.
• 14: A. Lubotzky and B. Weiss. Groups and expanders. In Expanding Graphs (ed. J. Friedman), DIMACS Ser. Discrete (MATH). Theoret. Compt. Sci. 10, pages 95--109. Amer. (MATH). Soc., 1993.
• 15: A. Mann. Positively finitely generated groups. Forum (MATH)., 8:429--469, 1996.
• 16: G. Margulis. Explicit construction of concentrators. Problems of Inform. Transmission, pages 325--332, 1973.
• 17: G. A. Margulis. Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators. Problems of Information Transmission, 24:39--46, 1988.
• 18: L. Pyber and A. Shalev. Groups with super-exponential subgroup growth. Combinatorica, 16:527--533, 1996.
• 19: O. Reingold , S. Vadhan , A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.3, November 12-14, 2000
• 20: R. Tanner. Explicit construction of concentrators from generalized N-gons. SIAM J. Alg. Discr. Meth., 5:287--293, 1984.
• 21: S. Wassermann. c*-algebras associated with groups with kazhdan's property T. Ann. (MATH)., 134:423--431, 1991.
• 22: B. Weisfeiler. Post-classification of jordan's theorem on finite linear groups. Proc. Nat. Acad. Sci. U.S.A, 81:5278--5279, 1984.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Generating functions

General Terms:
Algorithms, Experimentation, Performance, Theory