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/
Lectures
- [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)]
- [17 Feb: Anish] Outline of Math component of course
- [22 Feb: Lovy Singhal] Tutorial: Introduction to Haar measure, Finite
dimensional representation of groups.
- [29 Feb: Anish] Kazhdan's property (T)
- [7 Mar: Anish] SL(2,R) does not have property (T)
- [11 Mar: Lovy Singhal] Tutorial: Unitary
representations.
- [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)]
- [18 Mar: Prahladh] Error-Correcting Codes
Linear time decodable error-correcting codes: Sipser-Spielman
Codes.
Ref: [DH (Lec. 6), Gur, GI, SS, Zem]
- [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)]
- [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)]
- [7 Apr: Lovy Singhal] Tutorial: p-adic numbers.
Ref: [Rob (Sec I.2.4)]
- [8 Apr: Lovy Singhal] Tutorial: Iwasawa Decomposition and Dual
spaces.
Ref: [Bha (Lec. 1 and 7)]
- [11 Apr: Anish] SL(2,R)⋉R^2 and SL(3,R) have property
(T)
- [18 Apr: Anish] SL(3,Z) has property(T) and construction of
expander families from lattices.
- [25 Apr: Prahladh] Zig-zag and beyond
Undirected connectivity in logspace, lossless expanders via
lossless conductors.
Ref: [HLW (Sec 10), Kop (Lecture 11-12)]
- [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 )]
- [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.
- [Bha] R. Bhatia, Notes
on Functional Analysis, Texts and Readings in Mathematics, 50, Hindustan Book Agency 2009.
- [BHV] B. Bekka, P. de la Harpe, A. Valette, "Kazhdan’s
property (T)", New Mathematical Monographs, 11, Cambridge
University Press, 2008.
- [Bre] E. Breuillard, "Expanders
graphs, property (tau) and approximate groups", PCMI Lecture
Notes, Summer School, Utah, Jul 2012.
- [DH] C. Dwork, P. Harsha, "CS369E:
Expanders in Computer Science", Lecture notes for a course on
expanders at Stanford University, Spring 2005.
- [Gur] Venkatesan Guruswami. Error-correcting
codes and Expander graphs SIGACT News, 35(3): 25-41, September
2004.
- [GI] Venkatesan Guruswami, Piotr Indyk: "Linear
time encodable/decodable codes with near-optimal rate", IEEE Trans. Information Theory 51(10): 3393-3400 (2005).
- [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.
- [Kop] S. Kopparty, "Topics in Complexity Theory and Pseudorandomness", Rutgers, Spring 2013.
- [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)")
- [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.
- [Sha] Y. Shalom, The
algebraization of property (T), International Congress of
Mathematicians Madrid 2006.
- [Rob] A. M. Robert, A
Course in p-adic Analysis, Graduate Texts in Mathematics, 198,
Springer 2000.
- [Spi] Dan Spielman, "AM 561/CS 662:
Spectral Graph Theory", Yale, Spring 2015.
- [SS] Michael Sipser, Daniel A. Spielman:
Expander
codes. IEEE Transactions on Information Theory 42(6): 1710-1722
(1996).
- [Vad] S. Vadhan, "Pseuorandomness
(survey/monograph)", Foundations and Trends in Theoretical
Computer Science: Vol. 7: No. 1-3, pp 1-336.
- [Tre] L. Trevisan, "CS294:
A course on Expanders", UC Berkeley, Spring 2016.
- [Zem] Gilles Zemor: "On Expander
Codes", IEEE Transactions on Information Theory 47(2):835-837
(2001).
- [Zim] R. Zimmer, "Ergodic Theory
and Semisimple Groups", Monographs in Mathematics, Volume 81,
Springer 1984.
This page has been accessed at least
times since Jan 1, 2016.