Date | Presenter | Presenting |
---|---|---|

Aug 30th | Deeparnab Chakrabarty |
An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut TheoremLap Chi Lau Given an undirected multigraph G, and a set of required vertices S of V(G), the STEINER TREE PACKING problem is to find a largest collection of *edge disjoint* Steiner trees(1), each over the required set S. This problem is APX-hard (no PTAS unless P=NP). This paper gives a constant approximation ratio. In this talk, I shall show the main theorem of the paper which states the following: If the set S is 26k connected, then there are atleast k edge disjoint Steiner trees. In other words, if the minimum size of a Steiner cut(2) is 26k, then there are k edge disjoint Steiner trees. Interestingly, if the set S is the whole of V(G), that is the Steiner tree is actually a Spanning tree, then it follows as a simple corollary of the Nash-Williams-Tutte theorem (3) that if a graph is 2k connected then there are k edge disjoint Steiner trees. It is conjectured that the same is true for Steiner trees, but before this paper no constant times k was known. This paper uses a result of Frank etal which states: If a graph is 3k connected and there are no edges between two Steiner vertices, then the graph has k edge disjoint Steiner Trees. 1. A Steiner tree over a required set S is a tree which connects all the vertices in S 2. A Steiner cut is a cut which disconnects the required set 3. Nash-Williams-Tutte Theorem: A graph G has k edge-disjoint spanning trees iff for all partitions P = {V_1,V_2,...,V_t} of the vertex set, we have |E(P)| >= k(t-1) where E(P) are the edges across the partitions. |

Tuesday, Sept 7th, 4:45 (Note change of date and time) |
Nikhil Devanur |
Stochastic Optimization is (almost) as easy as deterministic
optimization. C. Swamy and D.B. Shmoys. (To appear in FOCS 2004). In this paper, the authors consider 2 stage stochastic optimization with recourse. These problems model the situations where there is uncertainty in the data. For instance, consider the vertex cover problem. In the first stage, only a probability distribution on the set of possible graphs is given, and the algorithm is allowed to pick some vertices (at the first stage cost). In the second stage, a graph is realised from the probability distribution, and the algorithm might have to pick additional vertices (at the second stage cost) to cover all the edges. The problem is to minimize the first stage cost plus the expected second stage cost. They consider the stochastic versions of set cover-type problems, in particular, set cover, vertex cover and facility location, and prove improved approximation ratios for these. The main technique invovles rounding and a modification of the ellipsoid algorithm, to solve an exponential sized Linear Program. |

Sept 13th | Nayantara Bhatnagar | Solving Convex Programs by Random Walks
Minimizing a convex function over a convex set in
n-dimensional space is a
basic problem with many interesting special cases. The authors present
a
simple algorithm for convex optimization given a separation oracle
using
sampling.Dimitris Bertsimas and Santosh Vempala It is a theorem that for any convex set K in R^n any halfspace containing the centroid contains at least 1/e fraction of the volume of K. The authors generalize this to show that for isotropic* convex sets any halfspace containing a point at distance t from the centroid contains at least 1/e - t fraction of the volume. Sampling uniformly from an isotropic convex set bounding the set of interest gives an approximate centroid. Thus a hyperplane separating the approximate centroid and the convex set will cut off at least a constant fraction of the volume. * A convex set is isotropic if its centroid is at the origin, and the expected distance squared in any direction is 1. |

Sept 20th | Nikhil Devanur |
A Polynomial Time Algorithm for Computing the Arrow-Debreu
Market Equilibrium for Linear Utilities.
Kamal Jain. (To appear in FOCS 2004.) In this paper, the author presents a polynomial time algorithm for computing the Market Equilibrium in the Arrow-Debreu model when the agents have linear utilities. Previously, only FPTASes were known for this problem. The author formulates the problem as a convex program, and shows that it can be solved using the ellipsoid method and diophantine approximation. However, these methods were only known to give an exact solution when the polyhedron is ``well-described''. This paper shows that this requirement can be weakened, and this weakening is sufficient to get an exact answer for the problem considered. |

Sept 27th | Yan Ding | Extracting Randomness from Few Independent SourcesBarak, Impagliazzo and Wigderson This paper is concerned with the problem of _deterministic_ extraction of near perfect randomness from _independent_ weak random sources. It is well known that deterministic extraction of randomness from a single general weak source is impossible, while explicit deterministic extractors from 2 independent sources were only known for entropy rate greater than 1/2. In this paper, the authors construct, for _any constant_ $\delta > 0$, a deterministic extractor from $poly(1/\delta)$ independent sources of entropy rate $\delta$. The construction employs tools from additive number theory, in particular a recent result of Bourgain, Katz and Tao. |

Oct 4th | Parikshit Gopalan | On the List and Bounded Distance Decodability of
Reed-Solomon CodesQi Cheng and Daqing Wan An [n,k]_q Reed Solomon code consists of all polynomials of degree at most k evaluted at n distinct point in the finite field F_q. Presently the best known decoding algorithms can recover a list of all codewords that agree with a received word at $t > \sqrt(nk)$ positions. It is not known whether one can do better, or even if the size of the list remains polynomially bounded for $t < \sqrt(nk)$. In this paper, the authors show a connection between the decoding problem for Reed Solomon codes and the discrete logarithm problem over certain extensions fields of F_q. They show for some parameter T (where k < T < \sqrt(nk)) that if there is a list decoding algorithm that recovers all codewords with T agreements, then there is an effecient algorithm for discrete log over an extension of F_q. |

Oct 11th | Vangelis Markakis | Tolls for heterogeneous selfish users in multicommodity
networks and generalized congestion games A model of selfish routing is considered, in which network
users route
traffic on paths that minimize their own cost (i.e. latency on the
edges
of the path + tolls), given the other users's choices. A multicommodity
flow resulting from such a routing is called a Nash equilibrium or a
Nash
flow. By using LP-duality theory, the authors show that it is possible
to impose tolls on the edges so that a Nash flow will minimize the
social cost which is the total latency of the network. The tolls can
be computed in polynomial time under certain assumptions on the
edge latency functions. This answers an open question posed by Cole,
Dodis and Roughgarden (STOC '03). It is also shown that the same
result holds even if the social cost is any nondecreasing function of
the congestion of the network. Finally their results are extended to
general congestion games. Fleischer, Jain and Mahdian Edge pricing of multicommodity networks for heterogeneous selfish users Karakostas and Kolliopoulos |

Oct 18th | Fall Break | |

Oct 27th | Tejas Iyer | Multilinear Formulas for Determinant and Permanent are of
Super-Polynomial SizeAn arithmetic formula is multi-linear if the polynomial
computed by each
of its sub-formulas is multi-linear. It is shown that any multi-linear
arithmetic formula for the permanent or determinant of an n x n matrix
is of size super-polynomial in n. Ran Raz, STOC 2004 |

Nov 8th | David Cash | Perfect Zero-Knowledge Arguments for NP Using any One-Way
PermutationIn cryptography it is often interesting to seek the minimal
assumptions required to build secure primitives. This paper
provides the first construction of perfect zero-knowledge proofs
with computational soundness from general assumptions. This
paper also introduces \emph{interactive hashing protocols}, which
have proven to be independently interesting.
Perfect zero-knowledge arguments allow a poly-time prover to convince
a verifier that a statement is true without leaking any other
information. This version of zero-knowledge proofs is interesting
cryptography, as it models the task where limited users must
authenticate
themselves with a more powerful untrusted server.Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung Journal of Cryptology, 1996 |

Nov 15th | Eric Vigoda | A mildly impractical algorithm for the permanentI'll present the proof (or as much as desired)
for the randomized poly-time algorithm to approximate the
permanent of an arbitrary non-negative matrix. I also
sketch some recent improvements (with Vijay and some others)
which leads to a O(n^7) time algorithm (ignoring a few log
factors).Jerrum, Sinclair, Vigoda + some recent work |

Nov 22th | Aranyak Mehta | AdWords and Generalized On-line MatchingAdvertising is the main source of revenue for search engine
companies such as Google. Each advertiser makes bids on specific
AdWords to Google and specifies his maximum daily budget, and is
charged whenever he wins a query placed on one of his chosen AdWords.
Should Google simply award each query to the highest bidder whose
budget is not exhausted? It is easy to show that this strategy
may achieve only half the value of the optimal allocation.
We introduce the notion of a tradeoff revealing LP and provide two
algorithms achieving a competitive ratio of 1 - 1/e for this problem
(which can be viewed as a generalization of the on-line matching
problem).
Our algorithms take into consideration the bid and the left-over budget
of advertisers. The optimal tradeoff between bid and budget is given by
the dual of the tradeoff revealing LP.
This is joint work with Amin Saberi, Umesh Vazirani, and Vijay
Vazirani.
Aranyak Mehta, Amin Saberi, Vijay Vazirani, Umesh Vazirani |

Dec 1st, 4:30 | Yan Ding | Cryptography in NC_0Applebaum, Ishai, Kushilevitz, FOCS 2004 This paper provides strong evidence for the existence of cryptographic primitives (e.g. one-way functions, pseudorandom generators, etc.) that can be computed by uniform NC0 circuits, in which each output bit depends on a _constant_ number of input bits. (An NC0 circuit is one which has polynomial size, constant depth, and constant fan-in.) More precisely, the paper shows that any OWF or PRG in Parity-L (which contains Log-Space) can be converted to one in NC0. The existence of such primitives in Parity-L follows from almost all number-theoretic or algebraic hardness assumptions. The technical tool of the paper is a method for randomized constant-degree and constant-locality encoding of functions in Parity-L that preserves security. |