Algorithms, Combinatorics and Optimization Seminars Schedule for Spring 2009

---

THURSDAY, February 5, 2009

Venkatesan Guruswami,U. Washington & CMU

Title: Combinatorics of list decoding linear codes

ABSTRACT: We discuss some (not so recent) combinatorial results concerning the asymptotic list decoding properties of *linear* codes. We will show the best known existential bounds on the trade-off between list-decodability and rate, which amounts to the following packing question: What is the largest size of a subspace C of the hypercube such that every Hamming ball of a certain radius contains at most L vectors of C? We will also briefly discuss the relation to the code's minimum distance: If every pair of vectors differ in at least a fraction \delta of coordinates, what is the largest radius for which every Hamming ball of that radius is *guaranteed* to have a small (polynomially bounded) number of vectors in it? The talk will be self-contained, and one of its principal objectives is to present some basic (and approachable) open questions in this topic.

Time:4:30 P.M.
Location:., WeH 5302

---

THURSDAY, March 19, 2009

Mike Neiman, Rutgers

TITLE: Negative correlation inequalities and log-concavity

ABSTRACT: Correlation inequalities are statements about how events in a probability space positively or negatively reinforce each other. After briefly discussing the better-understood theory of positive correlation, I will talk about some negative correlation inequalities and a potential relationship to celebrated conjectures of J. Mason about log-concavity properties of certain sequences arising from graphs and matroids. Along the way, I'll mention several interesting open problems.

Time: 4:30 P.M.
Location:Wean 5302