- Meeting 01 : Wed, Jan 15, 02:00 pm-04:00 pm - Narayanaswamy
| References | |
| Exercises | |
| Reading | |
The evaluation patten and policy. Mentioned the course webpage and the contents.
Material Discussed: Basic Probabilistic Method-Experiments, Outcomes, Probability of Outcomes. Experiments are samples from probability distributions. Random Variables, Expected Value of random variables, Linearity of Expectation, Markov's Inequality, Tchebyshev Inequality, Chernoff-Hoeffding bounds, Lovasz Local Lemma, Limited Independence Sample Spaces, Randomness Extractors, Random Walks and applications, Expander graphs.
An introduction the probabilistic method-
Introduced the MAX-CUT probabilistic.
Random color the vertices 0-1.
Expected number of non-monochromatic edges is half the number of edges in the graph.
There exists cuts of value half the number of edges.
Converting this existential argument into a deterministic algorithm that finds a cut of value at least half the number of edges.
| References: | The Probabilistic Method by Alon and Spencer.
Randomized Algorithms by Rajeev Motwani
|
| Reading: | Pairwise Independence and Derandomization by Luby and Wigderson. |
- Meeting 02 : Fri, Jan 17, 02:00 pm-04:00 pm - Narayanaswamy
| References | |
| Exercises | |
| Reading | |
Today we deal with a different distribution to solve the max-cut. We consider unit vectors assigned to the vertices so that for as many edges as possible, the vectors given to the vertices are orthogonal. No we pick a random hyperplane passing through the origin and partition the vertices based on the hyperplane. This yields a stronger result than half the number of edges. We then talk about the constructing pairwise independent sample spaces using the GF(2^t).
We then return to the basic probabilistic method and place lower bounds on R(k,k), existence of tournaments iwth property S_k, and the existence of dominating sets of a certain size in a graph G.
| References: | For the max-cut results, see Design of Approximation Algorithms by Shmoys and Williamson
For the the GF(2^t) based construction of pairwise independent sample spaces, see Luby and Wigderson
Rest is from Alon and Spencer
|
| Reading: | Design of Approximation Algorithms by Shmoys and Williamson
Pairwise Independence and Derandomization by Luby and Wigderson |
- Meeting 03 : Wed, Jan 22, 02:00 pm-04:00 pm - Narayanaswamy
| References | |
| Exercises | |
| Reading | |
Existence of tournament on n players satisfying a property that each k elements subset is defeated by one player. Upperbounds on the Size of a dominating set by sampling each vertex independently, and the connection to the greedy algorithm for finding a minimum dominating set.
| References: | Alon and Spencer, Chapter 1.
|
| Reading: | Probabilistic Lens: Erdos-Ko-Rao theorem. |
- Meeting 04 : Fri, Jan 24, 02:00 pm-04:00 pm - Narayanaswamy
| References | |
| Exercises | |
| Reading | |
Two colorability of n-uniform hypergraphs. Definition of m(n) the minimum number of of n-uniform hyperedges that can be there so that there is a the hypergraph is not 2 colorable. In otherwords, any u-uniform hypergrpah with for m(n)-1 hyperedges, is 2 colorable
A simple probabilistic argument shows that if there are less than 2^{n-1} edges then it is 2 colorable. Also, the presentation of a better lower bound. Using the probabilistic method to argue an upper bound on m(n)- fix a 2 coloring of the vertics and pick n-uniform hyperedges uniformly at random and ask for the probability that it is not a valid 2 coloring. Choose parameters to ensure that none of the 2 colors are valid for the randomly chosen instance. The number of sets chosen for this probability to be smaller than 1 is an upper bound on m(n).
| References: | Alon and Spencer
|
| Exercises: | Question if the number of edges in a n-uniform hypergraph is smaller than the lower bound m(n), can you find a 2 coloring?
|
- Meeting 05 : Wed, Jan 29, 02:00 pm-04:00 pm - Narayanaswamy
| References | |
| Exercises | |
| Reading | |
Balancing vectors: For any set of n unit vectors, the sum up random re-orientations by {0,pi}, results in a vector of length square-root of n. Theorems 4.1 and 4.2. Method of Alterations: sample from a distribution and alter. A different experiment to get a better bound on R(k,k). Then, the use of probabilistic method to give lower bound on maximum independent set size in sparse graphs (nd/2 edges, for some d)
| References: | Alon and Spencer
|
| Exercises: | Identify and algorithm for the multipliers in Theorems 4.1 and 4.2.
|
| Reading: | Turans Theorem after Chapter 6 in Alon and Spencer. |
- Meeting 06 : Fri, Jan 31, 02:00 pm-04:00 pm - Narayanaswamy
| References | |
| Exercises | |
| Reading | |
Focus on Chebyshev inequality. Universal hash families guaranteeing pairwise independence. For A,B subset of
set of t-bit strings, approximating the measure of A X B = |A||B|/2^{2t}. Use of Chebyshev Inequaltiy in estimating this measure, and the use of markov's inequality. Application to computing higher matrix powers, and application of higher matrix powers to derandomization via pseudorandom generators.
| References: | Tompa's notes on Randomized Algorithms and Pseudorandom generators
|
| Exercises: | The probabilistic lens: Bregman's theorem
|
| Reading: | The chapter on second moment in Alon and Spencer |
- Meeting 07 : Wed, Feb 05, 02:00 pm-04:00 pm - Narayanaswamy
| References | |
| Exercises | |
| Reading | |
Derandomizing space S(n) bounded randomized algorithms.
Model of RSPACE(S(n)) with one sided error and stopping in time 2^{S(n)}. Modeling computation of a randomized algorithm on an input as querying for an entry in the 2^{S(n)}-th power of an implicitly specified this matrix. Then using the hash lemma proved to argue that a randomly chosen h is good to approximate the square of this matrix. The distance measure between the approximate square matrix and the actual square matrix is formalized- using the statistical distance between 2 distributions assuming a 2 step random walk starts at a vertex. This is done for each vertex, and the worst distance is taken as the distance between the two matrices. Then the recursion is set up. Assuming that the hash functions are good at each recursive step, the accumulated error is bounded as a function of error of one squaring multiplied by an exponential in the number of recursion levels. Now, the bad event is that one hash function is bad in one of the recursion levels, the union bound is used, along with our chebyshev inequality result. This analysis also give us a structure of the psuedorandom generator.
| References: | Tompa's notes. Nisan's 1991 paper "Pseudorandom generator for Space bounded Computation".
|
- Meeting 08 : Fri, Feb 07, 02:00 pm-04:00 pm - Narayanaswamy
| References | |
| Exercises | |
| Reading | |
Statement of the Lovasz Local Lemma and proof. Simple application to Property B.
| References: | Alon and Spencer
|
- Meeting 09 : Wed, Feb 12, 02:00 pm-03:00 pm - Narayanaswamy
| References | |
| Exercises | |
| Reading | |
Symmetric version of the lovasz local lemma. Application to 2 coloring hypergraphs and connection to bounded occurence sat. SAT in whcih each variable occurs twice is easy can be reduced to matching in P time and also doable in log space. On the coloring of real numbers such that for any set S, every translate is multicolored.
| References: | Alon and Spencer
|
| Reading: | Satisfiability Problems Complete for Deterministic Logarithmic Space. STACS 2004: 317-325
Karpiniski's results on bounded occurence sat |
- Meeting 10 : Wed, Feb 19, 02:00 pm-04:00 pm - Narayanaswamy
| References | |
| Exercises | |
| Reading | |
Random walks on undirected graphs. Hitting time, cover time, commute time. Independence of a commute on the edges passed. Randomized Log space algorithm for undirected st connectivity.
| References: | Paper by AKLLR and notes by Tompa
|
| Reading: | http://dbwilson.com/mix/ is a very nice paper. |
- Meeting 11 : Fri, Feb 21, 03:00 pm-05:00 pm - Narayanaswamy
| References | |
| Exercises | |
| Reading | |
Geometric application of the lovasz local lemma. This is a result due to Pach and Levitska where we are asking for a tiling of the R^3 with unit disks. These are called k-covering, that is one in which each point is covered at least k times. What is known due to Pach is that if we know that each point is covered by at most t disks, then there is a decomposition of the disks into 2 sets such that each one is a covering.
| References: | Alon and Spencer.
|
