| Sep 4 |
Martin Pál PRIMES in P http://news.com.com/2100-1001-949170.html |
| Sep 11 |
Martin Pál PRIMES in P, part 2 |
| Sep 18 |
No TDG :-( |
| Sep 25 |
Alex Slivkins TITLE: O(n) min-vertex cuts with >2 components. ABSTRACT: It is easy to see that there can be exponentially many min-vertex cuts. Therefore it is quite surprising that there can be only O(n) min-vertex cuts with >2 components. This talk is based on two papers: Joseph Cheriyan, Ramakrishna Thurimella, "Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation" (STOC'96, J. Algorithms 33 (1999)). citeseer.nj.nec.com/cheriyan98fast.html. Tibor Jordan, "On The Number Of Shredders" (1997) (research report). citeseer.nj.nec.com/15620.html. |
| Oct 2 |
Ashwin Kumar Information-theoretically Secure Communication across Networks. We study the interplay of network connectivity and perfectly secure message transmission under the corrupting influence of generalized Byzantine adversaries. It is known that in the threshold adversary model, where the Byzantine adversary can corrupt upto any t among the n players (nodes), perfectly secure communication among any pair of players is possible if and only if the underlying synchronous network is (2t+1)-connected. Strictly generalizing these results to the non-threshold setting, we show that perfectly secure communication among any pair of players is possible if and only if the union of no two sets in the adversary structure is a vertex cutset of the synchronous network. The computation and communication complexities of the transmission protocol are polynomial in the size of the network and the maximal basis of the adversary structure. M V N Ashwin Kumar, Pranava R Goundan, K Srinathan, C. Pandu Rangan. On Perfectly Secure Communication over Arbitrary Networks, accepted to PODC 2002. |
| Oct 9 |
Anirban Dasgupta On the quality of spectral seperators (paper by Guattery and Miller). The authors explore the worst case examples for spectral analysis . They start with an example of a (bounded degree planar) graph in which the second eigenvector partitioning gives \theta(n) edge and vertex seperators, whereas the optimal bisection is constant sized. Then they describe a family of graphs which are bad for any "purely spectral" algorithm using only n^{\epsilon} eigenvectors. |
| Oct 16 |
Tom Wexler This week was an improvized session. Tom told us about the chromatic number of the unit-distance graph in R2 and Q2 (the set of nodes is equal to the set of points in the real/rational plane, edges between pairs of points with euclidean distance exactly 1) |
| Oct 23 |
Mark Sandler Title: Efficient zero-knowledge proofs Abstract: Zero-knowledge proof for language L is proofs when verifier gets convinced that given x is in L, while not getting any information, distinguishable from the information he can get by tossing coins. Most known zero-knowledge proof systems, for general NP languages, first construct a protocol that allows a prover to cheat with fixed probability 1/2, which is then iterated k times in order to achieve the required confidence (e.g. probability that prover is cheating) of level 1/2^k. These methods would require \Sigma(nk) bit commitments to the satisfiability of a boolean circuit of size n. One usually sets k equal to n, and making total number of commitments \Sigma(n^2) We will first consider some canonical examples of zero-knowledge proofs and then we will talk about [proper subset of] these two papers: Boyar, Brassard and Peralta, "Subquadratic Zero-Knowledge", J. of the ACM, Nov, 1995 and Ronald Cramer and Ivan Damgard: "Linear Zero Knowledge", from STOC'97 which discuss how to implement more efficient zero-knowledge proofs, namely proofs which require only O(n^3/2) and O(n) commitments. |
| Oct 30 |
Greg Bronevetsky Join me please on an incredible mystery tour through the wonders of Expander Codes. These plucky linear error correcting codes are efficient to decode, asymptotically good and are in general very cute. One the way we will encounter linear codes, expander graphs, expander codes and (time permitting) a linear time decoding algorithm. |
| Nov 6 |
STOC 03 paper submission deadline -- volunteers? :-) |
| Nov 13 |
Martin Pal I'll try to entertain you with the "linear algebra method", a technique to prove combinatorial lower bounds using linear algebra. Maybe we will even prove a lower bound on the chromatic number of the unit distance graph that Tom was talking about a couple of weeks ago. The lower bound is exponential in the dimension $n$. |
| Nov 20 |
No TDG due to FOCS. (ends Nov 19) |
| Nov 27 |
Thanksgiving -- no TDG |
| Dec 4 |
Elliot Anshelevich BGP Convergence Properties BGP is the routing protocol of the Internet. However, does BGP actually converge to some set of routes, or can it oscillate forever, congesting the network with unnecessary packets? We will explore this issue, state some necessary conditions for convergence, and also touch on an extension of BGP to a protocol in a more general graph model. |