# The ACO Seminar (2009-2010)

All talks on a combinatorial/discrete math/theoretical CS/not so theoretical CS/OR theme are welcome!

If you want to be a speaker or have questions or suggestions about the seminar, please contact
the organizers: Tom Bohman ( tbohman@andrew.cmu.edu )and David Offner ( offner@cmu.edu ).

Subscribe to the ACO seminar mailing list

## Past Schedule:

1995-96 1996-97 1998-99 1999-00 2000-01 2001-02 Fall 02 Spring 04 2004-05 2005-06 2006-07 2007-08 2008-09

## Current Schedule - Academic year 2009/10:

Title: Anatomy of a young giant component in the random graph
Speaker: Eyal Lubetzky, Microsoft Research
When: Thursday, September 10, 4:30-5:30
Where: Wean 6423
Abstract:
We provide a complete description of the giant component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$ as soon as it emerges from the scaling window, i.e., for $p = (1+\epsilon)/n$ where $\epsilon^3 n \to \infty$ and $\epsilon=o(1)$.

Our description is particularly simple for $\epsilon = o(n^{-1/4})$, where the giant component $C_1$ is contiguous with the following model (i.e., every graph property that holds with high probability for this model also holds w.h.p. for $C_1$). Let $Z$ be normal with mean $(2/3) \epsilon^3 n$ and variance $\epsilon^3 n$, and let $K$ be a random $3$-regular (multi)graph on $2\lfloor Z\rfloor$ vertices. Replace each edge of $K$ by a path, where the path lengths are i.i.d. geometric with mean $1/\epsilon$. Finally, attach an independent Poisson($1-\epsilon$)-Galton-Watson tree to each vertex. A similar picture is obtained for larger $\epsilon=o(1)$, in which case the random 3-regular graph is replaced by a random (multi)graph with $N_k$ vertices of degree $k$ for $k\geq 3$, where $N_k$ has mean and variance of order $\epsilon^k n$.

This description enables us to determine fundamental characteristics of the supercritical random graph. Namely, we can infer the asymptotics of the diameter of the giant component for any rate of decay of $\epsilon$, as well as the mixing time of the random walk on $C_1$.

Joint work with Jian Ding and Yuval Peres.

Title: Space Utilization of Cuckoo Hashtables
Speaker: Pal Melsted
When: Thursday, September 17, 4:30-5:30
Where: Wean 6423
Abstract:
We study the space requirements for Cuckoo Hashing. This can be reduced to the following question in Random Graphs.

We are given two disjoint sets L,R with |L|=n=alpha*m and |R|=m. We construct a random graph G by allowing each x in L to choose d random neighbours in R. The problem is to find m(G), the size of the largest matching in G.

From the point of view of Cuckoo Hashing, a key question is to locate the threshold for when m(G)=n with high probability, since if m(G) < n it is impossible to store all items. We answer this question exactly for d greater than 5.

Title: Lower Bounds on Error in Private Data Analysis and Connections to the Spectra of Random Matrices
Speaker: Adam Smith, Penn State
When: Thursday, September 24, 4:30-5:30
Where: GHC 7501 (note the unusual room)
Abstract:
Contingency tables are the method of choice of government agencies for releasing statistical summaries of categorical data. In this paper, we consider lower bounds on how much distortion (noise) is necessary in these tables to provide privacy guarantees when the data being summarized is sensitive. We extend a line of recent work on lower bounds on noise for private data analysis (DInur & Nissim, PODS 03; Dwork, McSherry & Talwar, STOC 07; Dwork and Yekhanin, Crypto 08) to a natural and important class of functionalities. Our investigation also leads to new results on the spectra of random matrices with correlated rows.

Joint work with Shiva Kasiviswanathan (Los Alamos) and Mark Rudelson (Michigan).

Title: On the 1-2-3 conjecture
Speaker: Michal Karonski, Emory University and Adam Mickiewicz University,
When: Thursday, October 22, 4:30-5:30
Where: Wean 6423
Abstract:
A weighting of the edges of a graph with integer weights gives rise to a weighting of the vertices, the weight of a vertex being the sum of the weights of its incident edges. Such a weighting induces a vertex coloring, i.e., by assigning the same color to vertices with the same weight. It is natural to consider edge weighting where we require that adjacent vertices have different weights --- that is, the vertex weighting induce a proper coloring of the graph.

Conjecture (Karonski, Luczak and Thomason, 2001): The edges of every graph that does not contain a component isomorphic to $K_2$ can be weighted with the integers {1,2,3} such that the resultant vertex weighting is a proper coloring.

In my talk I will discuss some recent developments regarding the above conjecture. and a related {1,2}-conjecture. In particular, I will present a joint result, with Maciej Kalkowski and Florian Pfender, showing that {1,2, ... , 5}-edge-weighting suffices to properly color vertices of a graph.

Title: Chasing robbers on random graphs
Speaker: Pawel Pralat, West Virginia University,
When: Thursday, October 29, 4:30-5:30
Where: Wean 6423
Abstract:
We study the vertex pursuit game of Cops and Robbers where cops try to capture a robber on the vertices of the graph. The minimum number of cops required to win on a given graph G is the cop number of G. We present asymptotic results for the game of Cops and Robber played on a random graph G(n,p) for a wide range of p=p(n). It has been shown that the cop number as a function of an average degree forms an intriguing zigzag shape.

Title: Set systems without a strong simplex
Speaker: Zed Yilma
When: Thursday, November 12, 4:30-5:30
Where: Wean 6423
Abstract:
A d-simplex is a collection of d+1 sets such that every d of them have non-empty intersection and the intersection of all of them is empty. A strong d-simplex is a collection of $+2 sets A,A_1, ... ,A_{d+1} such that {A_1, ... ,A_{d+1}} is a d-simplex, while A contains an element of each d-wise intersection. For n large and k \geq d+2, we prove that a k-uniform hypergraph F that contains no strong d-simplex has size at most {n-1 \choose k-1} with equality only when F is a star. Joint work with Tao Jiang and Oleg Pikhurko. Title: Proof of the Bollobas-Catlin-Eldridge conjecture Speaker: Gabor Kun, DIMACS and Institute for Advanced Study When: Thursday, November 19, 4:30-5:30 Where: Wean 6423 Abstract: We say that the graphs G and H with n vertices pack if G and H can be embedded to the same vertex set with no overlapping edges. Bollobas, Eldridge and independently Catlin conjectured that if that if (M(G)+1)(M(H)+1) < n+2 holds for the maximal degress then G and H pack. Aigner and Brandt and independently Alon and Fischer proved this in the case M(G),M(H)<3. Csaba, Shokoufandeh and Szemeredi proved it if M(G),M(H)<4. Bollobas, Kostochka and Nakprasit settled the case when one of the graphs is degenerate. Kaul, Kostochka and Yu showed that if M(G)M(H)<3/5n and the maximal degrees are large enough then G and H pack. We prove the conjecture for graphs with at least 10^8 vertices. Title: Phase transition of uniform random graphs: Erd"os-R'enyi graphs vs planar graphs Speaker: Mihyun Kang, Technische Universitaet Berlin, When: Thursday, December 3, 4:30-5:30 Where: Wean 6423 Abstract: Since the seminal work of Erd"os and R'enyi the phase transition of the largest components in random graphs became one of the central topics in random graph theory and discrete probability theory. In this talk we discuss the similarity and difference of critical behaviour of the largest components in the Erd"os and R'enyi random graph and in a uniform random planar graph. Title:Faster Generalized Flow via Interior Point Algorithms Speaker: Sam Daitch, Yale Univeristy, When: Thursday, January 14, 4:30-5:30 Where: GHC 7501 Abstract: We present fastest known algorithms for various network flow problems. In particular, we consider the well-known maximum flow and minimum-cost flow problems, as well as the generalized versions of these problems. In the generalized versions, a multiplicative factor is associated with each edge, defining the relationship between the amount flowing in and the amount flowing out of the edge. Our algorithm deals with "lossy" generalized flow networks, where the multiplicative factors are at most 1. We obtain an additive epsilon approximation for the lossy generalized max flow and min-cost flow problems in time O(m^(3/2)log^2(U/epsilon)) (excluding log(m) factors) for graphs with m edges, and with integer capacities and costs in the range {1...U} and loss multipliers that are ratios of integers in the same range. Furthermore, for the standard max-flow and min-cost flow problems we obtain exact algorithms that run in time O(m^(3/2)log^2(U)) (excluding log(m) factors). For the standard min-cost flow problem, and for the lossy generalized max flow and min-cost flow problems, our algorithms are faster than the previously best known by a factor of roughly O(m^(1/2)). The above algorithms work by accelerating traditional interior point algorithms by quickly solving the linear equations that arise in each step. The running times rely on our analysis of the performance of interior-point algorithms when each step is computed using an approximate solver. In particular, for network flow problems, to obtain the results described above it suffices to approximately compute each interior-point step in nearly linear time. In standard flow problems, the system of linear equations arising at each interior-point step is described by a symmetric positive-semidefinite diagonally-dominant matrix. Such systems can be solved in nearly linear time using an algorithm of Spielman and Teng. In the generalized flow problems, the linear systems from the interior-point steps are described by symmetric M-matrices. We present an algorithm for solving linear systems in symmetric M-matrices in nearly-linear time. Our algorithm reduces the problem of solving a linear system in a symmetric M-matrix to that of solving a logarithmic number of linear systems in symmetric diagonally-dominant matrices. By speeding up interior-point algorithms using the Spielman-Teng algorithm (in the standard flow case) and our M-matrix algorithm (in the generalized flow case) we obtain the flow algorithms stated above. Title: Positional Games Speaker: Michael Krivelevich, Tel Aviv University When: Thursday, January 28, 4:30-5:30 Where: Wean 5310 Abstract: The theory of positional games is a branch of combinatorics, whose main aim is to develop systematically an extensive mathematical basis for a variety of two player perfect information games, ranging from such commonly popular games as Tic-Tac-Toe and Hex to purely abstract games played on graphs and hypergraphs. In this talk I will survey basic notions and concepts of positional games and some recent developments in the field, putting an emphasis on interconnections between positional games and other branches of mathematics and computer science, in particular probabilistic considerations. Title: Upper tails for counts of random objects Speaker: Andrzej Rucinski, A. Mickiewicz University and Emory University When: Thursday, March 4, 4:30-5:30 Where: Wean 5310 Abstract Title: A Dichotomy Theorem for Graph Homomorphisms with Complex Values Speaker: Jin-Yi Cai, University of Wisconsin-Madison When: Thursday, April 1, 4:30-5:30 Where: Wean 5310 Abstract: Graph homomorphism (Lov\'{a}sz 1967) has been studied intensively by many researchers over the decades. The problem can be stated as follows: Given an$m \times m$symmetric matrix$A$over the complex field, compute the function$Z_A(\cdot)$, where for an arbitrary input graph$G$, Z_A(G) = \sum_{\xi:V(G)\rightarrow [m]} \prod_{(u,v)\in E(G)} A_{\xi(u),\xi(v)}. The problem encompasses many interesting combinatorial problems. We prove a complexity dichotomy theorem, that every problem in this class is either computable in P or \#P-hard, depending in$A\$. The complex field affords much possibility for cancelations and thus non-trivial polynomial time algorithms. Indeed Fourier matrices and character sums play a major role. In the complex domain, there are also natural connections to holographic algorithms. Due to the complexity of the proof, we will only be able to give a rough outline.

Joint work with Xi Chen of Princeton and Pinyan Lu of Tsinghua. Paper available on http://arxiv.org/abs/0903.4728 (111 pages.)

Title: List decodability of random linear codes
Speaker: Venkat Guruswami
When: Thursday, April 22, 4:30-5:30
Where: Wean 5310
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.

Title: New Approximation Algorithms for the Asymmetric Traveling Salesman Problem
Speaker: Amin Saberi, Stanford University
When: Thursday, April 29, 4:30-5:30
Where: Wean 5310
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.

Title: Minicourse on ZDDs. This lecture follows Prof. Knuth's Katayanagi Prize lecture .
Speaker: Donald Knuth , Stanford University
When: Thursday, May 6, 4:30-5:30
Where: GHC 8102

PostScript Ghostview or GSview, Adobe Acrobat Reader, Sun StarOffice Impress or Microsoft PowerPoint Viewer.