Probabilistic Methods in Computer Science

Instructor: Stasys Jukna (V 210)
E-mail: jukna@ti.uni-trier.de

Lecture: Wednesday 14:00-15:30 (V 302)
Labour: Wednesday 16:00-17:30 (V 302)

Vorlesungsankündigung [HTML]
The info page (1 page, ps)

Topics:

1. "Warm-up ..." 
Maximum satifiability problem for 2-CNFs
Experiment, Sample space, random variable, event
Balls in Bins (some training)
Expected value, conditional probabilty, variance
Finite stochastic processes 
2. "Counting Sieve" 
Graphs without large cliques
Monochromatic arithmetical progressions
Tournments
Maximum satisfiability revised - MaxSat
k-satisfiable CNF's
3. "Randomized Algorithms" 
Verifying polynomials
Schwartz Lemma
Randomness in communication
Equivalence of branching programs
A MIN-CUT algorithm
4. "Derandomization" 
General frame, Adleman's theorem
Method of conditional probabilities
Applications: legal colourings for set systems, the MAX-CUT problem. 
5. "Linearity of Expectation" 
Hamiltonian paths in tournments
Degree and Independence numbers for graphs
6. "The deletion method" 
Bounds for Ramsey numbers
Turan's Theorem
Points without obtuse triangles
Colouring large girth graphs
7. "Second Moment Method" 
The method: variation, expectation and Chebyshev's inequality
Threshold for 4-cliques
The Erdos-Renyi threshold
Covering designs
8. "Lovasz Local Lemma" 
Dependency Graphs; the Local Lemma
Two applications: Red-Blue colourings
9. "Entropy" 
Concentration property and conditional entropy
The subadditivity of entropy
Applications in Extremal Set Theory
10. "Random Walks" 
Walks in graphs and Word Search Problems
Long words over small alphabet
Short words over large alphabet