RANDOM GRAALS 2003 2nd Bertinoro Workshop on Random(ized) Graphs and Algorithms
15-20 June 2003 |
![]() |
---|
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 |
Arrival: | Sunday 15 June 2003 |
---|---|
Departure: | Saturday 21 June, 2003 |
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.
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 |
![]() |
Almost Random Graphs with Simple Hash Functions
(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
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
Modeling the Internet Graph
Degree distribution of Hub-Authority web graphs
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
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
Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
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
ANALYTIC DEPOISSONIZATION AND ITS APPLICATIONS
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
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.
TBA
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
(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
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
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
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
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
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
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
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
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
ABSTRACTS
by Martin Dietzfelbinger, Technical University of Ilmenau
by Nicola Galesi, Universitat Politècnica de Catalunya
by Claire Kenyon, Universitè Paris-Sud
by Christos Papadimitriou, University of California at Berkeley
by Colin Cooper, King's College, London
by Michael Mitzenmacher, Harvard
by Riccardo Zecchina, International Centre for Theoretical Physics, Trieste
by Mary Cryan, University of Leeds
by Artur Czumaj, New Jersey Institute of Technology
by Wojciech Szpankowski, Purdue University
by Stefano Leonardi, La Sapienza of Rome
by Michal Karonski, Adam Mickiewicz University and Emory University
by Tom Bohman, CMU
by Gregory Sorkin, IBM TJ Watson
by Gopal Pandurangan, Purdue University
by
Dimitris Achlioptas, Microsoft
by Michael Krivelevich, Tel Aviv University
by Yossi Azar, Tel Aviv University
by Susanne Albers, University of Freiburg
by Uri Feige, Weizmann Institute
by Berthold Voecking, University of Dortmund
by Cynthia Dwork, Microsoft Research