Mathematical Methods in Computer Science


Gil Kalai and Avi Wigderson

Class Hours: Sunday 12-2, Sprinzak 117

Office hours: Coordinate via email. Gil: Avi:

picture from class

Course Requirements: 50% - lecture notes , 50% - final exam

Lecture notes coordinator: Boaz Barak. Email:

Bulletin Board:
  • Exercises 1&3 are on-line.
  • If you want credit for the course, send email to Boaz with the dates you can take lecture notes.
  • You should submit the notes not later than 2 weeks after the lecture.

    • Contents:

  • Lecture Notes

  • Exercises

  • Course Plan

  • References

    • Lecture Notes

  • Instructions how to write the lecture notes: pdf format , postscript format.

  • A good example of lecture notes from a course of Oded Goldreich small bias sample spaces (postscript) (written by Yehuda Lindell & Alon Rosen).

  • Dowload the template files: lecture0.tex , lecture0.bib, lnotes.sty

    • (To see how the template compiles with the graphics you will need to download also the files lec0_example.eps and lec0_example.jpg)

    Click here for useful links regarding writing the lecture notes.

    Table of Lectures and Scribes:
    Lecture
    No.         		Date Topic Scribes Notes
    1 16/2 Explicit constructions, Ramsey graphs Romina Guelman and Eyal Bigman -
    2 23/2 Bipartite Ramsey graphs Romina Guelman and Eyal Bigman -
    3 2/3 epsilon-bias, 2-source extractors Yuval Sharon and Ofek Shilon -
    4 9/3 alternative Ramsey construction, defs of explicitness, ECC Ittai Chorev, Eyal Fistenberg -
    5 16/3 Shannon capacity, Intro to Simplex Algorithm Eran Nevo -
    6 23/3 Simplex algorithm (cont.) Dudu Statter and Benny Kimmelfeld -
    7 30/3 Simplex algorithm (cont. 2) Dudu Statter and Benny Kimmelfeld -
    8 6/4 --- Dvir Falik and Yehonatan Samet -
    9 27/4 NO CLASS -- -
    10 4/5 --- Tomer Weksler -
    11 11/5 --- Dvir Falik and Yehonatan Samet -
    12 18/5 --- Dvir Falik and Yehonatan Samet -
    13 25/5 --- Boaz Barak -
    14 1/6 --- Adi Shraibman -
    15 8/6 --- Yehonatan Bilu -

    Useful Links:

    Examples of lecture notes to learn from: Linial & Wigderson's Course on Expander Graphs , Goldreich's Course on Complexity Theory.

    LaTeX resources and tutorials: Boaz's LaTeX links

    Search for BibTeX citations: Collection of Computer Science Bibliographies (for CS papers), AMS MR Lookup (for other mathematics papers).

    Exercises

    The exercise number corresponds to the lecture number.

  • Exercise 1: .ps file .pdf file LaTeX file
  • Exercise 3: .ps file .pdf file LaTeX file

    • Course Plan

    This plan is very tentative and should not be taken too seriously...

    Explicit constructions:
    Definitions of prob and explicit const
    Ramsey numbers
    Frankl-Wilson (Noga - Shannon capacity) e^{\sqrt log n}
    Gromlos construction
    Bibpartite Ramsey - Hadamard matrices
    Zarankiewicz, Norm graphs, unbalanced Ramsey
    Discrepancy sets (for combinatorial rectangles)
    Expanders
    Extractors

    Linear Programming:
    Graph of polytope
    Diameter problem
    Randomized simplex algorithm
    Duality (perhaps for e-nets). MinMax for games and complexity of randomized algorithms.
    algorithms for Equilibria of games
    Perceptron algs for LP (Dunagan-Vampala)

    Topological methods:
    Kahn-Saks-Sturtevant
    Saks-Zagrgolou, Herlihy-Shavitt
    Benor (Minlor-Thom)
    Bjorner-Lovasz-Yao
    Kneser graphs - Lovasz thm

    e-nets & learning:
    e-nets, VC dim, fractional set cover (Komlos), PAC learning
    weak e-nets
    Hard-core set & learning DNFs under unif dist(Boosting)
    PAC learning of DNF's?

    Codes:
    Def, motivation, constructions, bounds
    Codes from lossless expanders
    Locally decodable/testable codes

    Matrices:
    Rigidity (& lower bounds)
    Rank vs Communication Complexity (Quantum cc, analogy to deg vs dec tree)
    Matrix mult, verification prob&Det
    Matching alg & verification of poly identities. Derandomization?
    Parallelization?

    Polynomials:
    Lower bounds on const depth circuits
    Poly method for existence. Algorithmic search??
    Polys vs decision trees

    Entropy:
    Shearer lemma - Jaikumar
    Minc conj - Jaikumar
    Kahn-Kim alg for poset sorting
    Compression - Lempel-Ziv
    Hashing, extractors

    Random walks:
    Broder, Jerrum-Sinclair
    Conductance, isoperimetric ineq, electrical networks, connectivity

    References

    Books:

    Jiri Matousek Lectures on Discrete Geometry - contains material on linear programming, duality and e-nets.

    R. Motwani & P. Raghavan Randomized Algorithms - contains material on small sample spaces.

    Papers:

    J. Naor & M. Naor Small-bias Probability Spaces: efficient constructions and Applications - construction of e-bias spaces.

    N. Alon, O. Goldreich J. Hastad and R. Peralta Simple Constructions of Almost $k$-wise Independent Random Variables - different construction of e-bias spaces. See also addendum to this paper.

    Frankl, P.; Wilson, R. M. Intersection theorems with geometric consequences. Combinatorica 1 (1981), no. 4, 357--368 - best explicit construction of a Ramsey graph.

    M. Naor Constructing Ramsey graphs from small probability spaces - a different construction of a Ramsey graph.

    N. Nisan, S. Rudich, M. Saks Products and Help Bits in Decision Trees - lower bound for decision trees with help bits.

    A.C.C.Yao "Probabilistic Computations: Towards a unified measure of complexity", FOCS 77, pp. 222-227, 1977 - contain "minimax" argument for reducing lower bounds for probabilistic algorithms to average case lower bounds for determinstic algorithms.

    Page maintained by Boaz Barak