Department of Computer Science and Engineering, IIT Kharagpur 721302, India
=============================================================================
Dated: November 17, 2007
======================
First lecture 20/07/07 10:30 am Room 302 CSE Top Floor.
Second lecture Thursday 8:30 am Room 302 CSE Top Floor.
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
[Special Topics on Algorithms: CS60035, LTP 3-0-0, 3 credits: Autumn 2007]
Evaluation: 20 for teacher's assessment, 30 for midsems and 50 for endsems as per rules.
--------------------------------------------------------------------------------------
Teaching Assistant: Nitin Kumar (M. Tech. 2006-2008)
--------------------------------------------------------------------------------------
Registrants
==============
Mridul Aanjaneya, Arindam Khan, Anupam Prakash, Abhigyan, Nitin Goyal, Vikas Kumar, Vinayak Pathak, Arijit Ghosh and Dipendra Pratap Singh.
=====================
[Not restricted to] Proposed topics:
=======================
Use of the probabilistic method in the design and analysis of algorithms and protocols, and demonstration of upper and lower bounds on combinatorial complexities of structures.
Combinatorial and computational issues in geometric visibility.
Classical and quantum communication complexity.
Problems and applications of graph and hypergraph theory.
Succint and efficient coding and counting of combinatorial structures.
Multi-dimensional hypergraph drawing/embedding.
Topics on network flows, special data structures for geometric algorithms and algorithms from visibility and some combinatorial geometry problems.
=======================================
Instructor: Sudebkumar Prasant Pal
=======================================
TEXTS and REFERENCES:
=============================
(i) Motwani, R. and Raghavan, P., Randomized Algorithms, Cambridge University Press.
(ii) Chazelle, B., The Discrepancy Method: Randomness and Complexity, Cambridge University Press.
(iii) Ghosh, S. K., Visibility Algorithms in the Plane, Cambridge University Press.
(iv) Bollabas, B., Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability, Cambridge University Press, 1986.
(v) Graham, R. L., Rothschild and Spenser, J., Ramsey Theory, John Wiley and Sons, 1980.
(vi) Kushilevitz, E., and Nissan, N., Communication Complexity, Cambridge University Press, 1997.
(vii) Molloy and Reed, Graph Coloring and the Probabilistic Method, Springer, 2002.
(viii) Pach, J., and Agarwal, P., Combinatorial Geometry, John Wiley and Sons, 1995.
(ix) Alon, N. and Spencer, J., The probabilistic method, John Wiley and Sons, Inc., 2000.
(x) Edelsbrunner, H., Algorithms for Combinatorial Geometry, Springer.
(xi) M. I. Shamos and F. P. Preparata, Computational Geometry: An Introduction, Springer.
========================================================================
Elements of the Probabilistic Method
-------------------------------------------------------
Hypergraphs, Simplices and Geometric Graphs (Updated August 10, 2007)
-------------------------------------------------------
-------------------------------------------------------
Assignment 1: Sumbission by August 06, 2007
========================================================================
Seminar and term paper projects:
=================================>
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Each student must have a comprehensive write-up submitted by October 29, 2007. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
(1) Random walks, quantum random walks and their applications in the design of randomized and quantum algorithms-- Arijit Ghosh
Highlights:
================
Random walks in 2-d and in 3-d: for 2-d, the expected number of times one gets back to the origin is unbounded, whereas this is not the case for higher dimensions. These results were explained. Appications were alluded to. [October 11, 2007]
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
(2) Probabilistic methods and colorings-- Anupam Prakash
Highlights:
===================
(i) Sum-free subset cardinality lower bound was derived. (ii) Superconcentrators of O(n log n) and linear size were demonstrated; the first one explicitly and the second one only by establishing existence. [October 12, 2007]
Expanders and Superconcentrators
===================================
Expander graphs are sparse graphs with very good connectivity properties. For any subset S of an expander graph the number of edges in the cut induced by S and its complement is at least k.|S|, k a constant. We present a proof for the existence of a family of bipartite expander graphs with 36n edges and k=1 using probabilistic methods.
Expander graphs find numerous applications in theoretical computer science. They have been used to design error correcting codes, pseudorandom generators, randomness extractors, hash functions for cryptography and superconcentrators. They are also used in the proofs of important results in complexity like the PCP theorem.
A superconcentrator of order n is a directed graph which has n input and output nodes. It has the property that for any choice of k input and output nodes there are k mutually edge disjoint paths between them. We use the expander graph whose existence we proved to construct a superconcentrator with of order n having O(n) vertices. We also look into some of the properties of expanders and superconcentrators.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
(3) Triangulations and tesselations in projective spaces and tiling: Succinct coding for tesselations-- Mridul Aanjaneya [October 26, 2007]
Highlights:
===================
Title:
========
Succinct Encodings for Geometric Tessellations
Abstract:
========
The importance of coding theory in Computational and Combinatorial Geometry was emphasized. Counting schemes for triangulations of point sets based on "smart" encodings was demonstrated, specifically for 1xn lattice triangulations, and hinted for general point sets giving references of known bounds. Two different coding schemes for 2xn domino tilings were explained and their relation to determining flip-distance between tilings was elucidated. Finally, a general scheme for proving connectivity in the space of all tilings was shown by considering and proving the result by Pak and Korn of local connectivity of T-Tetromino tilings from Height Functions and Chain Graphs.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
(4) Discrepancy theory methods with applications in establishing combinatorial bounds in hypergraph theory and in combinatorial or convex geometry-- Vinayak Pathak
Highlights:
===================
Vinayak considered linear and heirarchical discrepancies and developed the geometric interpretation towards the establishment of the relationship between them.
A notion of discrepancy was defined for hypergraphs and a few examples were given to form an intuition about what kind of a property discrepancy represents. It was realised that though it may appear that the discrepancy of a hypergraph measures its complexity, it is not necessarily the case and therefore, two more types of discrepancies - hereditary discrepancy and linear discrepancy - were defined. The definitions were then stated in terms of the incidence matrix of the hypergraph. The idea was then used to form elegant pictorial representations using convex sets for the three kinds of discrepancies. The pictorial representations showed an important relationship between them.
[Wednesday, October 31, 2007, 9:30 am - 10:30 am]
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
(5) Dipendra Prasad Singh
1. Antichain property
2. Sperner's theorem
3. Proof of Sperner's theorem by Lubell
4. Lovasz's theorem
5. Theorem of Bollobas
6. Orignal proof of Sperner's theorem,
For reference first two chapters of book "Combinatorics of finite sets" by Ian Anderson was refered.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
(6) Vikas Kumar [Friday, November 2, 2007, 10:30 am - 12:30 pm]
Highlights:
===================
Combinatorial discrepancy upper and lower bounds.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
(7) Abhigyan [November 9, 2007]
Point-location methods like those of Preparata, Kirkpatrick and others, possibly including techniques such as fractioning cascading.
In my seminar, I presented the Chain Method proposed by Lee and Preparata (1976). It takes O(log^2 (n)) time instead of the O(log(n)) optimal solution. The optimal solution can be achieved by applying fractional cascading to the chain method, which yields the Bridged Chain method. (Edelsbrunner, Guibas, Stolfi (1986).) From this, some possible branches of further study are 1. Other Appications of Fractional Cascading 2. Point Location problem for higher dimensions 3. Dynamic Point Location - data structure which also supports the insertion and deletion operations on the point set efficiently. I will present few other techniques for point location problems and some dynamic point location methods in the term paper for this course.
Reference material for my seminar: Computational Geometry : Preparata and Shamos
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
(8) Nitin Goyal [November 9, 2007]
Firstly, I considered the Ham-Sandwich theorem for solid objects in two-dimensions, also known as the Pancake Theorem. The proof goes by defining two distance functions from the center of a unit circle centered at origin using the bisectors of the two solid objects in the direction perpendicular to a diameter of the circle. Then, the proof follows from the continuity argument of the difference of the two functions.
Later, we considered the extention of the proof to n-dimensions and proved the Ham-Sandwich theorem for n objects in n-dimensions. The Borsuk-Ulam theorem was used by defining a a continuous function from an (n-1)-sphere to the n-1 dimensional Euclidean space.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
(9) Studies on centerpoints, Ham-Sandwich cuts and related convex geometry with appications-- Arindam Khan [Thursday, Novemvber 2, 2007, 11:30 am - 12:30 pm]
Highlights:
===================
"Weighted Ham Sandwich Cuts and 3-SUM Hard Problems" based on:
1. Algorithms for Ham-Sandwich Cuts [Chi-Yuan Lo, J. Matougek, and W. Steiger 1994]
2. Weighted Ham-Sandwich Cuts [Prosenjit Bose and Stefan Langerman 2005 ]
3. On a class of O( n^2) problems in computational geometry [Anka Gajentaan, Mark H. Overmars 1995]
4. Generalizations of the Theorems of Radon, Helly and Caratheodory [V. W. Bryant and R. J. Webster 1968],
The first part of the presentation will contain different algorithms and approaches for normal/weighted Ham Sandwich cuts. Determining whether Weighted Ham-Sandwich cut is unique (developed by Bose-Langerman ) is 3-SUM Hard. So, the next part of the presentation will cover definitions and few interesting 3-SUM hard problems. The proof also needs some basic concepts of duality and pruning, which will also be covered.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
==========================================================
Further topics could be:
(i) Random walks on expanders and their applications in algorithm design.
(ii) Derandomization and pseudorandomness.
(iii) k-sets in 2-space and 3-space. [Tamal Dey's result inclusive.]
========================================================================
Lecture contents:
===================
27/7/07
Basic concepts about hypergraphs and amortized analysis of algorithms using potential functions: Here we discussed a couple of examples including the example of a binary counter of n-bits. We proved a constant amortized cost per increment of the counter by using the number of bits set to 1 as the potential function. We discussed the problem of 2-4 trees and showed that over a series of n insertions, the amortized cost per insertion is O(1), where the potential function was defined to be the number of nodes with 4 children. We also discussed motivations for the problem of hypergraph bicoloring.
2/8/07
Notion of the first moment method used to show that a hypergraph H with atleast k vertices per hyperedge and fewer than 2^(k-1) hyperedges is 2-colorable in the sense that there will be no monochromatic hyperedges. We discussed a very simple Las Vegas algorithm for bicoloring similar sparse hypergraphs with less than 2^(k-3) hyperedges. Started to look at techniques used to derandomize the algorithm to come up with a polytime deterministic algorithm for the problem.
3/8/07
Completed discussion on the derandomised polytime bicoloring algorithm. Introduced the case of hypergraph bicoloring where first moment principle will fail but Lovasz's Local lemma can be used to prove bicolorabilty: we withdrew the restriction of the number of hyperedges but constrained the number of hyperedges that a particular hyperedge is allowed to intersect with (that is, have a common vertex with). We discussed the problem of bicolability in the case of hypertrees. We also touched upon the problem of List coloring in an ordinary graph: Given an ordinary graph with n vertices such that we assosiate a list of colors to each vertex and constrain the vertex to be colored with one of the colors from its designated list.
9/8/07
==============
Started the discussion on the Ramsey's theorem in the general setting for hypergraphs and the Erdos-Szekeres theorem.
================================
23/08/2007
================================
Optimal bounds for hypergraph bicoloring games: The lower bound using pigeon-hole principle, the upper bound using a probabilistic argument. As an offshoot, we have a rudimentary probabilistic proof of a version of the pigeon-hole principle.
================================
24/08/2007 (Part I)
================================
Use of the first moment method as well as the local lemma to derive upper bounds on the number of strategies needed to solve the coloring game. The bound obtained may be asymptotically comparable but the constants of proportionality may be different ! We can also check what happens when the uniformity of the complete hypergraphs considered are functions of the number of vertices against what happens when they are constant.
================================
24/08/2007 (Part II)
================================
Introduction to arrangement of lines in 2-space and the zone theorem. Linear bounds for sum of degrees (of faces) and sum of squares of degrees. Introduction to planar point location queries and data structures. Deterministic construction of data structures as well as probabilistic constructions using the random sampling technique (to be continued).
================================
================================
31/08/2007
================================
Many faces complexity of an arrangement of lines: The use of Kovari-Sos-Turan's result of the upper bound on the number of edges in a bipartitite directed graph devoid of K_{s,t}, other bounds using the notion of average of squares of degrees. Hints about the lower bound using Euler's phi function, and allusion to (the random sampling) optimal upper bound (to be continued).
================================
05/09/2007
================================
Techniques for bounding problem solution sizes in divide-and-conquer recurrences: introduction to median finding, centerpoints in d-space (the proof of existence using Helly's theorem), the combination lemma for segment arrangements in 2-space, the Lipton-Tarjan Separator theorem, and the polygon cutting theorem by Chazelle.
================================
September 13, 2007
===================
Ham-sandwich cuts help in answering half-planar range queries in sublinear query time. Straightforward use can further be refined saving some lines for improved performance.
Exercises for homework: prune-and-search for median finding and ham-sandwich cuts.
How we use the continuous density functions for proving the two-set common bisector theorem.
================================
Oct 04, 2007
================
We wish to count incidences of faces on n defining lines where m faces are selected from the arrangement of the n lines.
First we solve a different problem, as in Thm 11.2 of [Pach and Agarwal]. This relates to random sampling as was done by Clarkson et al. When the random sample of r lines is taken from n lines, the average number of lines (out of n-r lines) intersecting a trapezoid of the arrangement of the r lines, is small. So, there exists a choice of r lines with such a small incidence, of the order of n/r.
================================
Oct 05 2007 double lecture.
==============================
The many faces complexity for an arrangement of n lines and m points; Canham's bound is used, and Thm 11.2 is used in each trapezoid of the "good" random sample. Then, the parameter r is fixed to a suitable value to get the cherished upper bound.
================================
November 01, 2007
=====================
The notion of transversals (vertex covers) and packings (matchings) on hypergraphs; the notion of fractional analogues of such parameters; the inequalities governing them and the linear progarmming duality; approximating the transversal number using Lovasz's result for bounded degree hypergraphs [Pach and Agarwal].
The uniqueness criteria of the Radon point for specific cases; the uniqueness of the Radon partition for specific cases; the implications of such cases may be studied for deep consequences in combinatorial geometry.
================================
Details of lectures on, September 6, 7 and 14, and August 16, 17 and 31 upcoming.