|
Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department |
Algorithms, Combinatorics and Optimization Seminars
Schedule for Spring 2010
THURSDAY, March 4, 2010 Andrzej Rucinski, Emory and A. Mickiewicz Universities Title: Upper tails for counts of random objects ABSTRACT: Let S be a family of subsets of a finite set \Gamma and let \Gamma_p be a binomial random subset of \Gamma. Further, let X count the number of members of S contained in \Gamma_p. A lot of research has been devoted to the study of the asymptotic distribution of X when N =|\Gamma| \to \infty and p=p(N), both, in the general setting and for special instances, most notably for random graphs. One feature which has received a lot of attention is the rate of decay of the tails of X, the lower tail Prob(X\le tE X) for 0<t<1, and the upper tail Prob(X\ge tE X) for t>1. Good estimates for the lower tail follow from the FKG inequality (lower bound) and Janson's inequality (upper bound). The upper tails tend to be harder to analyze. For the subgraph count problem a quite satisfactory and complete result was obtained by Janson, Oleszkiewicz, and Ruci\'nski, where the logarithms of the upper and lower bound on Prob(X\ge tE X) are of the same order of magnitude except for a logarithmic term. A generalization to random hypergraphs was carried over by Dudek, Polcyn, and Ruci\'nski. In this talk I will show how, using the proof techniques developed earlier, those results are extended in two directions. First, we examine the more general model of set systems (hypergraphs) and obtain some straightforward estimates for the upper tail of X, covering, among others, the number of arithmetic progressions of given length in a random subset of integers. Then, we return to the subgraph counts in random graphs to study the \emph{rooted} version of the problem, only to discover some unexpected features there. This is joint work with Svante Janson. Time: 4:30 P.M. - 5:30 P.M. THURSDAY, April 22, 2010 Venkat Guruswami, Computer Science Dept., Carnegie Mellon University Title: List decodability of random linear codes ABSTRACT: For every fixed finite field F_q, 0 < p < 1-1/q, and epsilon > 0, we prove that with high probability a random subspace C of F_q^n of dimension (1-h_q(p)-epsilon)n has the property that every Hamming ball of radius pn has at most O(1/epsilon) elements of C. (Here h_q(x) is the q-ary entropy function.) This answers a basic open question concerning the list-decodability of linear codes, showing that a list size of O(1/epsilon) suffices to have rate within epsilon of the ``list decoding capacity'' 1-h_q(p). This matches up to constant factors the list-size achieved by general (non-linear) random codes, and gives an exponential improvement over the best previously known list-size bound of q^{O(1/epsilon)}. The main technical ingredient in our proof is a strong upper bound on the probability that m random vectors chosen from a Hamming ball centered at the origin have too many (more than O(m)) vectors from their linear span also belong to the ball. The talk will be self-contained and not assume any coding theory background. Joint work with Johan Hastad and Swastik Kopparty. Time: 4:30 P.M. - 5:30 P.M. THURSDAY, April 29, 2010 Amin Saberi, Stanford University Title: New Approximation Algorithms for the Asymmetric Traveling Salesman Problem ABSTRACT: I will talk about new approximation algorithms for the Asymmetric Traveling Salesman Problem (ATSP). Our approach is based on constructing a ``thin'' spanning tree from the solution of a classical linear programming relaxation of the problem and augmenting the tree to an Eulerian subgraph. I will talk about a conjecture on the existence of such trees and its relations to the graph embedding literature and nowhere-zero flows. Our first result is an O(logn/loglogn) approximation algorithm for the problem that uses a new type of randomized rounding. Our rounding method is based on sampling from a ``maximum-entropy'' distribution which could be of independent interest. The second result focuses on a special case where the underlying undirected graph of the LP relaxation of the problem has bounded genus. This is the case for example, when the distance functions are shortest paths in a city with few bridges and underpasses. We derive a constant factor approximation algorithm in that case. Time: 4:30 P.M. - 5:30 P.M.
|
