If you

Subscribe to the ACO seminar mailing list

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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

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:

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:

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:

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

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.