Expanders: constructions and their applications - Winter/Summer Semester (2015-16)

Time: Mon 14:00-17:30 (with a 30 min break 15:00-15:30)
Location: G77 (TIFR)
Instructors : and
Homepage: http://www.tcs.tifr.res.in/~prahladh/teaching/2015-16/expanders/

Course Announcement

Lectures

  1. [Jan 15: Prahladh] Introduction, motivation and examples
    Administrivia; 3 motivating examples: superconcentrators, error-correcting codes and error-reduction of one-sided error randomized algoithms; spectral connection; examples of expanders.
    Ref: [HLW (Sec. 1), DH (Lec. 1), Vad (Sec. 4.1.1 and 4.3.1)]

  2. [17 Feb: Anish] Outline of Math component of course

  3. [22 Feb: Lovy Singhal] Tutorial: Introduction to Haar measure, Finite dimensional representation of groups.

  4. [29 Feb: Anish] Kazhdan's property (T)

  5. [7 Mar: Anish] SL(2,R) does not have property (T)

  6. [11 Mar: Lovy Singhal] Tutorial: Unitary representations.

  7. [14 Mar: Prahladh] Expanders -- the spectral connection
    Spectral expansion implies vertex expansion, expander mixing lemma, Cheeger's inequalities.
    Ref: [DH (Lec. 2), , Vad (Sec. 4.1.1 and 4.1.2), Tre (Lec. 3-4)]

  8. [18 Mar: Prahladh] Error-Correcting Codes
    Linear time decodable error-correcting codes: Sipser-Spielman Codes.
    Ref: [DH (Lec. 6), Gur, GI, SS, Zem]

  9. [28 Mar: Prahladh] Random walks on expanders
    Random walks in (general) undirected graphs, undirected connectivity is in randomized logspace (Aleliunas et. al.), Pseudo-random generators: AKS generator.
    Ref: [DH (Lec. 3-4), Vad (Sec. 4.2)]

  10. [4 Apr: Prahladh] Zig-Zag expanders
    Operations on graphs: squaring, tensoring, replacement product, zig-zag product; Construction of expanders using zig-zag product.
    Ref : [Vad (Sec 4.3.2-4.3.3)]

  11. [7 Apr: Lovy Singhal] Tutorial: p-adic numbers.
    Ref: [Rob (Sec I.2.4)]

  12. [8 Apr: Lovy Singhal] Tutorial: Iwasawa Decomposition and Dual spaces.
    Ref: [Bha (Lec. 1 and 7)]

  13. [11 Apr: Anish] SL(2,R)⋉R^2 and SL(3,R) have property (T)

  14. [18 Apr: Anish] SL(3,Z) has property(T) and construction of expander families from lattices.

  15. [25 Apr: Prahladh] Zig-zag and beyond
    Undirected connectivity in logspace, lossless expanders via lossless conductors.
    Ref: [HLW (Sec 10), Kop (Lecture 11-12)]

  16. [2 May: Prahladh] Bipartite Ramanujan expanders for all degrees - I
    2-lifts of graphs; eigen spectrum of lifts; matching polynomials and its properties.
    Ref: [MSS, Spi (Lec. 25-26 )]

  17. [9 May: Prahladh] Bipartite Ramanujan expanders for all degrees - I
    Interlacing polynomials and their properties.
    Ref: [MSS, Spi (Lec. 22 and 26)]

References

The links below point to the actual location of papers at the author's homepages or other electronic repositories and the papers are not reposted locally.

  1. [Bha] R. Bhatia, Notes on Functional Analysis, Texts and Readings in Mathematics, 50, Hindustan Book Agency 2009.
  2. [BHV] B. Bekka, P. de la Harpe, A. Valette, "Kazhdan’s property (T)", New Mathematical Monographs, 11, Cambridge University Press, 2008.
  3. [Bre] E. Breuillard, "Expanders graphs, property (tau) and approximate groups", PCMI Lecture Notes, Summer School, Utah, Jul 2012.
  4. [DH] C. Dwork, P. Harsha, "CS369E: Expanders in Computer Science", Lecture notes for a course on expanders at Stanford University, Spring 2005.
  5. [Gur] Venkatesan Guruswami. Error-correcting codes and Expander graphs SIGACT News, 35(3): 25-41, September 2004.
  6. [GI] Venkatesan Guruswami, Piotr Indyk: "Linear time encodable/decodable codes with near-optimal rate", IEEE Trans. Information Theory 51(10): 3393-3400 (2005).
  7. [HLW] S. Hoory, N. Linial, A. Wigderson, "Expander graphs and their applications", Bulletin of the American Mathematical Society, vol. 43, no. 4, pp. 439-561, 2006.
  8. [Kop] S. Kopparty, "Topics in Complexity Theory and Pseudorandomness", Rutgers, Spring 2013.
  9. [Laf] V. Lafforgue, "Un renforcement de la propriété (T) [French]" (Translation: Strengthening of the property (T)), Duke Math. J., 143(3):559--602, 2008. (see also: B. Liao, "Strong Banach property (T), after Vincent Lafforgue", arXiv:1212.4646 and A. N. Aaserud. "Lafforgue's new proof that SL(3,R) has Kazhdan's property (T)")
  10. [MSS] Adam W. Marcus, Daniel A. Spielman, Nikhil Srivastava, Interlacing families I: Bipartite Ramanujan graphs of all degrees, Annals of Mathematics, 182 (1), pp. 307-325. 2015.
  11. [Sha] Y. Shalom, The algebraization of property (T), International Congress of Mathematicians Madrid 2006.
  12. [Rob] A. M. Robert, A Course in p-adic Analysis, Graduate Texts in Mathematics, 198, Springer 2000.
  13. [Spi] Dan Spielman, "AM 561/CS 662: Spectral Graph Theory", Yale, Spring 2015.
  14. [SS] Michael Sipser, Daniel A. Spielman: Expander codes. IEEE Transactions on Information Theory 42(6): 1710-1722 (1996).
  15. [Vad] S. Vadhan, "Pseuorandomness (survey/monograph)", Foundations and Trends in Theoretical Computer Science: Vol. 7: No. 1-3, pp 1-336.
  16. [Tre] L. Trevisan, "CS294: A course on Expanders", UC Berkeley, Spring 2016.
  17. [Zem] Gilles Zemor: "On Expander Codes", IEEE Transactions on Information Theory 47(2):835-837 (2001).
  18. [Zim] R. Zimmer, "Ergodic Theory and Semisimple Groups", Monographs in Mathematics, Volume 81, Springer 1984.

This page has been accessed at least several times since Jan 1, 2016.

Prahladh Harsha
Valid HTML 4.01! Valid CSS!