2nd Bertinoro Workshop on Random(ized) Graphs and Algorithms

15-20 June 2003
University of Bologna Residential Center
Bertinoro (Forlì), Italy

[ What the Meeting is About
| Seminar Schedule
| Important Dates
| Location
| How to Reach Bertinoro
| List of Participants
| Abstracts
| Organization and Sponsorship
Local Weather Forecast]

What the Meeting is About

Random graphs and randomized algorithms continue to play a very important role in algorithmic research and discrete mathematics. This meeting will be an opportunity to focus on some recent developments and discuss open problems, old and new.

Talk Schedule

08.00-09.00 arrivals breakfast
09.15-10.00 Papadimitriou Kenyon Dietzfelbinger Karonski Feige departures
10.00-10.30 coffee coffee coffee coffee coffee
10.30-11.15 Naor Achlioptas Dwork Bohman Cooper
11.15-12.00 Cryan Vigoda Mitzenmacher Pandurangan Galesi
12.30-13.30 lunch! lunch! lunch! lunch! lunch!
15.00-15.45 Czumaj Zecchina Albers Vöcking TBA
15.45-16.00 coffee coffee coffee coffee coffee
16.00-16.45 Leonardi Azar Szpankowski Sorkin Krivelevich

Important Dates

Arrival: Sunday 15 June 2003
Departure: Saturday 21 June, 2003


The meeting will be held in the small medieval hilltop town of Bertinoro. This town is in Emilia Romagna about 50km east of Bologna at an elevation of about 230m.  Here is a map putting it in context. It is easily reached by train and taxi from Bologna and is close to many splendid Italian locations such as Ravenna, a treasure trove of byzantine art and history, and the Republic of San Marino (all within 35km) as well as some less well-known locations like the thermal springs of Fratta Terme and the castle and monastic gardens of Monte Maggio.  Bertinoro can also be a base for visiting some of the better-known Italian locations such as Padua, Ferrara, Vicenza, Venice, Florence and Siena.

Bertinoro itself is picturesque, with many narrow streets and walkways winding around the central peak.  The meeting will be held in a redoubtable ex-Episcopal fortress that has been converted by the University of Bologna into a modern conference center with computing facilities and Internet access.  From the fortress you can enjoy a beautiful the vista that stretches from the Tuscan Apennines to the Adriatic coast.

How to Reach Bertinoro

List of participants.

Organization and Sponsorship

Scientific Organizing Committee Alan Frieze Carnegie Mellon University
Michael Mitzenmacher Harvard University
Eli Upfal Brown University
Local Organization
Andrea Bandini, Elena Della Godenza,, Centro Congressi di Bertinoro
Sponsored by BICI   Bertinoro International Center for Informatics


Almost Random Graphs with Simple Hash Functions
by Martin Dietzfelbinger, Technical University of Ilmenau

(joint work with Phillipp Woelfel)

We describe a simple randomized construction for generating pairs of hash functions $h_1,h_2$ from a universe $U$ to ranges $V=[m]=\{0,1,\ldots,m-1\}$ and $W=[m]$ so that for every key set $S\subseteq U$ with $n=|S| \le m/(1+\epsilon)$ the (random) bipartite (multi)graph with node set $V \uplus W$ and edge set $\{(h_1(x),h_2(x))\mid x \in S\}$ exhibits a structure that is essentially random. The construction combines $d$-wise independent classes for $d$ a relatively small constant with the well-known technique of random offsets. While keeping the space needed to store the description of $h_1$ and $h_2$ at $O(n^\zeta)$, for $\zeta<1$ fixed arbitrarily, we obtain a much smaller (constant) evaluation time than previous constructions of this kind, which involved Siegel's high-performance hash classes. The main new technique is the combined analysis of the graph structure and the inner structure of the hash functions, as well as a new way of looking at the cycle structure of random (multi)graphs. The construction may be applied to improve on Pagh and Rodler's ``cuckoo hashing'' (2001), to obtain a simpler and faster alternative to a recent construction of {\"O}stlin and Pagh (2002/03) for simulating uniform hashing on a key set $S$, and to the simulation of shared memory on distributed memory machines. Complementing the main construction, we also describe a novel way of implementing (approximate) $d$-wise independent hashing without using polynomials.

Space Complexity of Random Formulae in Resolution
by Nicola Galesi, Universitat Politècnica de Catalunya

We prove that for $\Delta \geq 1$ and any $\epsilon > 0$, with high probability a random $k$-CNF over $n$ variables and $\Delta n$ clauses requires resolution clause space of $\Omega(n / \Delta^{1+\epsilon})$.

As a consequence, we get the first lower bound for size of treelike resolution refutations of random $3$-CNFs with clause density $\Delta > > \sqrt{n}$.

To prove the space lower bound, we: (1) introduce a 2-player Matching Game on bipartite graphs $G$ to prove that there are no perfect matchings in $G$; (2) reduce space lower bounds for a formula $F$ in Resolution to lower bounds for the complexity of the game played on the bipartite graph $G(F)$ associated with $F$; (3) prove that the complexity of the game is large whenever $G$ is an expander graph.

Joint work with E. Ben-Sasson.

A randomized PTAS for metric minimum bisection
by Claire Kenyon, Universitè Paris-Sud

Modeling the Internet Graph
by Christos Papadimitriou, University of California at Berkeley

Degree distribution of Hub-Authority web graphs
by Colin Cooper, King's College, London

We derive the age dependent degree distribution for various models of web graphs. One application of this is to obtain the asymptotic power law(s) for the distribution of in and out degree of a model of directed web-graphs which conforms to the Hub-Authority model

New Exhaustive, Heuristic, and Interactive Approaches to Rectangular Strip Packing
by Michael Mitzenmacher, Harvard

We consider the two-dimensional rectangular strip packing problem. Computers are especially efficient at producing and evaluating possible packings of a given set of rectangles. However, the characteristics of the search space appear to make it not amenable to standard local search techniques, such as simulated annealing or genetic algorithms. A standard simple heuristic, Bottom-Left-Decreasing, has been shown to handily beat these more sophisticated search techniques.

We present several new approaches to the problem. We show that a branch-and-bound-based exhaustive search is much more effective than previous methods for problems with less than 30 rectangles when the rectangles can be tightly packed with little or no unused space. For larger problems, we introduce and demonstrate the effectiveness of a natural improvement to the Bottom-Left-Decreasing heuristic.

Furthermore, we observe that while the search space for this problem appears difficult for computers to navigate, people seem able to reason about it extremely well. This is unsurprising in that people are known to outperform computers at packing irregular polygons in industrial applications. We incorporate our new algorithms in an interactive system that combines the advantages of computer speed and human reasoning. Using the interactive system, we are able to quickly produce significantly better solutions than previous methods on benchmark problems.

From analytical results on random k-sat to a message-passing algorithm for satisfiability
by Riccardo Zecchina, International Centre for Theoretical Physics, Trieste

Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
by Mary Cryan, University of Leeds

We consider the problem of sampling almost uniformly from the set of contingency tables with given row and column sums, when the number of rows is a constant. Cryan and Dyer previously gave a fully polynomial randomized approximation scheme (fpras) for the related counting problem, which only employs Markov chain methods indirectly. But they left open the question as to whether a natural Markov chain on these tables mixes rapidly. We answer this question in the affirmative, and hence provide a very different proof of the result of Cryan and Dyer. We show that the "2-by-2 heat-bath" Markov chain is rapidly mixing. We prove this by first considering a heat-bath chain operating on a larger window. Using techniques developed by Morris for the multidimensional knapsack problem, we show that this chain mixes rapidly. We then apply the comparison method of Diaconis and Saloff-Coste to show that the 2-by-2 chain is rapidly mixing. To establish this, we provide the first proof that this chain mixes in time polynomial in the input size even when both the number of rows and number of columns are constant.

Estimating the weight of metric minimum spanning trees in sublinear-time
by Artur Czumaj, New Jersey Institute of Technology

by Wojciech Szpankowski, Purdue University

In analysis of algorithms and combinatorics often a Poisson version of a problem is easier to solve than the original model called usually the Bernoulli model. Poissonization replaces a deterministic input by a random one, thus making the analysis more tractable while depoissonization interprets the results in terms of the original model. In fact, depoissonization is a Tauberian result for the Borel mean that we call the Poisson transform. In our talk, we shall discuss several analytic depoissonization results and their numerous applications (e.g., digital trees, multiaccess protocols, probabilistic counting, selecting a leader, data compression such as Lempel-Ziv schemes). Most our results fall into the following general scheme: If the Poisson transform of a sequence has an appropriate growth in the complex plane, then an asymptotic expansion of the sequence can be expressed in terms of the Poisson transform and its derivatives evaluated on the real line. We also formulate some general central limit theorems for the Poisson and Bernoulli models. All our findings are based on analytic techniques such as functional equations, generating functions of complex variable, the Mellin transform, and the Cauchy formula.

Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm
by Stefano Leonardi, La Sapienza of Rome

Spielman and Teng invented the concept of smoothed analysis to explain the success of algorithms that are known to work well in practice while presenting poor worst case performance. Spielman and Teng [STOC 01] proved that the simplex algorithm runs in expected polynomial time if the input instance is smoothened with a normal distribution. We extend this notion to analyze online algorithms. In particular we introduce smoothed competitive analysis to study the Multi-Level Feedback (MLF) algorithm, at the basis of the scheduling policies of Unix and Windows NT, when the processing times of jobs released over time are only known at time of completion.

We show that, if the k least significant of K bits describing the processing time of a job are randomly changed, MLF achieves a tight smoothed competitive ratio of O(2K-k) to minimize the average flow time. A direct consequence is a first constant approximation for this problem in the average case under a quite general class of probability distributions.

by Michal Karonski, Adam Mickiewicz University and Emory University

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 weighting induces a vertex coloring, i.e., vertices with the same weight are assigned the same colour. If we require that {\em adjacent} vertices have different weights, then the induced vertex weighting is a proper colouring of the graph. We ask the following question.

Is it possible to weight the edges of any non-trivial graph (i.e., a connected graph with at least three vertices) with the integers $\{1,2,3\}$ such that the resultant vertex weighting is a proper colouring?}

In my talk I will offer two pieces of information in relation to the question. Firstly, that a weighting is possible for $3$-colourable graphs, and secondly that, if real, rather than just integer, weights are permitted, then a finite number of weights suffices for all graphs. The proof of the later result is a combination of deterministic and probabilistic techniques.

This is joint work with Tomasz Luczak and Andrew Thomason.

A Phase Transition for Avoiding a Giant Component
by Tom Bohman, CMU

(Joint work with Jeong Han Kim)

Abstract. Let $ (e_1, f_1), \dots, (e_{cn}, f_{cn}) $ be a sequence of ordered pairs of edges from the complete graph on $n$ vertices chosen uniformly and independently at random. The goal here is to choose one edge from each pair to form a graph which contains no giant component (i.e. a component of size order $n%). Here we prove the existence of a critical value $c_0$ for the off-line version of the problem: If $ c > c_0 $ then with high probability every graph that consists of one edge from each pair has a giant component, and there is a (randomized, off-line) algorithm for the choice of one edge from each pair that produces a graph that with high probability has no giant if $ c < c_0 $.

Faster algorithms for Max Cut and Max 2-CSP, with polynomial expected time for sparse cases
by Gregory Sorkin, IBM TJ Watson

co-authored with Alex Scott (UCL).

We show that a maximum cut, in an n-vertex random graph with edge density 1/n or less, can be found in polynomial expected time. We actually prove a more general result: that a random instance of a weighted Max2CSP (a maximum constraint satisfaction problem whose clauses are over pairs of binary variables) is solvable by a deterministic algorithm in polynomial expected time, in the "sparse" regime where the expected number of clauses is half the number of variables.

Our method is to show, first, that if a Max2CSP has a connected underlying graph with n vertices and m edges, the solution time can be deterministically bounded by 2 to the power (m-n)/2. Then, a branching-process analysis of the tails of the distribution of m-n, for a component of a random graph, yields our result.

An alternative deterministic bound on the solution time, as 2 to the power m/5, improves upon a series of recent results.

Random Graphs in Peer-to-Peer Networks
by Gopal Pandurangan, Purdue University

Random graphs and random graph-theoretic ideas have turned out to be useful in designing efficient Peer-to-Peer (P2P) networks. In this talk, I will discuss two provably good P2P design schemes which illustrate this theme: (1) an efficient distributed and local scheme to build low-diameter P2P networks and (2) a fault-tolerant P2P network which provides low-latency and low-bandwidth data accessing schemes. The first scheme is motivated by the classical Erdos-Renyi random graph model, while the second scheme exploits random embedding of trees and the small-world phenomenon in social networks.

Scheme (1) is joint work with P. Raghavan and E. Upfal and Scheme (2) is joint with S. Jagannathan, and S. Srinivasan.

On the Threshold of Random k-SAT and Property B
by Dimitris Achlioptas, Microsoft

For k>2, let H=H(n,m) be a random k-uniform hypergraph on n vertices formed by adding m hyperedges one by one, each hyperedge chosen uniformly and independently among all "n choose k" possible hyperedges. A random k-CNF formula F is constructed from H by "negating" each vertex in each edge with probability 1/2. Let us say that an event occurs with high probability (w.h.p.) if it occurs with probability that tends to 1 as n tends to infinity. Assume that m = cn and write T = 2^{k-1} ln2. It is well-known that H is w.h.p. non-2-colorable if c = T and F is w.h.p. unsatisfiable if c = 2T.

We prove that for every k>2: H is w.h.p. 2-colorable if c = T - 1. F is w.h.p. satisfiable if c = 2T - k.

Based on joint work with Cris Moore and Yuval Peres.

Adding random edges to dense graphs
by Michael Krivelevich, Tel Aviv University

In this talk I will discuss a novel model of random graphs. In this model, a large graph H=(V,E) on n vertices, usually with bounded minimum degree, is given, and a set R of m edges is chosen uniformly at random from the set of non-edges of H to form a random graph G=(V,E+R). The question is then: how large should be the value of m to guarantee the almost sure appearance of various monotone properties in G?

Here we treat the case where the minimum degree of H is linear in n. We consider such properties as existence of a fixed size clique, diameter, k-connectivity, and Ramsey properties, and obtain tight results for most of the problems.

A joint work with Tom Bohman, Alan Frieze, Ryan Martin (Carnegie Mellon University), and with Prasad Tetali (GeorgiaTech).

Reducing Truth-telling Online Mechanisms to Online Optimization
by Yossi Azar, Tel Aviv University

We describe a general technique for converting any deterministic on-line algorithm for any resource allocations problem (the goal is to maximize the value of accepted requests) to a randomized on-line truthtelling mechanism (i.e., requests may not disclose their real values and our goal is to maximize the total income collected from accepted requests) with a small additive degradation in the performance. The result is applied for on-line routing and admission control and for combinatorial auctions.

Joint work with Baruch Awerbuch and Adam Meyerson (STOC 2003).

Dynamic TCP Acknowledgement: Penalizing Long Delays
by Susanne Albers, University of Freiburg

We study the problem of acknowledging a sequence of data packets that are sent over a TCP connection. Previous work on the problem has focused mostly on the objective function that minimizes the sum of the number of acknowledgements sent and the delays incurred for all of the packets. In this talk we investigate a new objective function that minimizes the sum of the number of acknowledgements sent and the maximum delay incurred for any of the packets. This function is especially interesting if a TCP connection is used for interactive data transfer between network nodes. We present deterministic online algorithms that achieve an optimal competitive ratio and give lower bounds on the performance of randomized algorithms. (Joint work with Helge Bals; presented at SODA 2003.)

On the sum of nonnegative independent random variables with unbounded variance
by Uri Feige, Weizmann Institute

Let $X = \sum_{i=1}^n X_i$ be a random variable equal to the sum of arbitrarily many nonnegative independent random variables. Then we show that regardless of the variance of the random variables, there is reasonable probability that $X$ does not exceed its expectation by much. More specifically, we show that $Pr[X \le E[X] + \max_i[E[X_i]]] \ge c$, where $c > 0$ is some universal constant independent of $n$. A motivating application (quickly finding loaded components in networks) will be described.

Random Knapsack in Expected Polynomial Time
by Berthold Voecking, University of Dortmund

We present the first average-case analysis proving an expected polynomial running time for an exact algorithm for the 0/1 knapsack problem. In particular, we prove, for various input distributions, that the number of dominating solutions (i.e., Pareto-optimal knapsack fillings) to this problem is polynomially bounded in the number of available items. An algorithm by Nemhauser and Ullmann can enumerate these solutions very efficiently so that a polynomial upper bound on the number of dominating solutions implies an algorithm with expected polynomial running time. The random input model underlying our analysis is very general and not restricted to a particular input distribution. We assume adversarial weights and randomly drawn profits (or vice versa). Our analysis covers general probability distributions with finite mean, and, in its most general form, can even handle different probability distributions for the profits of different items. This feature enables us to study the effects of correlations between profits and weights. Our analysis confirms and explains practical studies showing that so-called strongly correlated instances are harder to solve than weakly correlated ones.

Joint work with Rene Beier.

Spam-Fighting : the Science
by Cynthia Dwork, Microsoft Research

The online set cover problem
by Seffi Naor, Technion

Consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm one-by-one. Once a new element is given, the algorithm has to cover it by some set containing it. We assume that the elements and sets are known in advance to the algorithm, however, the actual set of elements given by the adversary is not known in advance to the algorithm, and may be only a strict subset of the total set of elements. The objective is to minimize the total cost of the sets chosen by the algorithm. The performance of the algorithm is defined to be the ratio between the cost of the algorithm and the optimal cost restricted to the given set of elements. We present an $O(\log m \log n)$ competitive deterministic algorithm for the problem, and establish a nearly matching $\Omega\left( \frac{\log n \log m}{\log \log m + \log \log n}\right)$ lower bound for all interesting values of $m$ and $n$. The techniques used are motivated by similar techniques developed in computational learning theory for online prediction (e.g., the WINNOW algorithm) together with a novel way of converting the fractional solution they supply into a deterministic. Extensions and generalizations will be discussed as well.

Joint work with Noga Alon, Baruch Awerbuch, Yossi Azar, and Niv Buchbinder.

A Non-Markovian Coupling for Sampling Colorings
by Eric Vigoda, University of Chicago

We study a simple Markov chain, known as the Glauber dynamics, for randomly sampling (proper) k-colorings of an input graph G=(V,E) with maximum degree D and girth g. We prove the Glauber dynamics is close to the uniform distribution after O(nlogn) steps whenever k>(1+\eps)D, for all \eps>0, assuming g>10 and D=\Omega(logn), where n=|V|. The best previously known bounds were k>11D/6 for general graphs, and k>1.489D for graphs satisfying girth and maximum degree requirements.

Our proof relies on the construction and analysis of a non-Markovian coupling. This appears to be the first application of a non-Markovian coupling to substantially improve upon known results.

This is joint work with Tom Hayes (University of Chicago).

Maintained by Alessandro Panconesi