********************************
*** WEIZMANN-WARWICK MEETING ***
***        ABSTRACTS         ***
********************************


*** MEETING'S WEBPAGE ***

http://www.wisdom.weizmann.ac.il/~robi/seminars/WeizmannWarwickMeeting-2010_12.html



****************************************
*** SUNDAY (algorithmic game theory) ***
****************************************

Speaker: Yossi Azar, Tel Aviv University
Title: How to Allocate Goods in an Online Market?

Abstract:
We study an online version of Fisher's linear case market. In this
market there are $m$ buyers and a set of $n$ dividable goods to be
allocated to the buyers. The utility that buyer $i$ derives from good
$j$ is $u_{ij}$. Given an allocation $\hat{U}$ in which buyer $i$ has
utility $\hat{U}_i$ we suggest a quality measure that is based on
taking an average of the ratios $U_{i}/\hat{U}_i$ with respect to any
other allocation $U$. We motivate this quality measure, and show that
market equilibrium is the optimal solution with respect to this
measure. Our setting is online and so the allocation of each good
should be done without any knowledge of the upcoming goods.

We design an online algorithm for the problem that is only worse by a
logarithmic factor than any other solution with respect to our
proposed quality measure, and in particular competes with the market
equilibrium allocation. We prove a tight lower bound which shows that
our algorithm is optimal up to constants. Our algorithm uses a primal
dual convex programming scheme. To the best of our knowledge this is
the first time that such a scheme is used in the online framework.

Joint work with Niv Buchbinder and Kamal Jain.

---

Speaker: Troels Sørensen, University of Warwick
Title: Computational complexity of equilibrium refinements

Abstract: 
The king of refinements of Nash equilibrium is trembling hand
perfection. We show that it is NP-hard and Sqrt-Sum-hard to decide if
a given pure strategy Nash equilibrium of a given three-player game in
strategic form with integer payoff is trembling hand
perfect. Analogous results are shown for a number of other solution
concepts, including proper equilibrium, (the strategy part of)
sequential equilibrium, quasi-perfect equilibrium and CURB. The proofs
all use a reduction from the problem of comparing the minmax value of
a three-player game in strategic form to a given rational number. This
problem was previously shown to be NP-hard by Borgs et al., while a
Sqrt-Sum hardness result is given in this paper. The latter proof
yields bounds on the algebraic degree of the minmax value of a
three-player game that may be of independent interest.

This is joint work with Kristoffer Arnsfelt Hansen and Peter Bro
Miltersen, both at Aarhus University.

---

Speaker: Michal Feldman, Hebrew University and microsoft Israel R&D Center. 
Title: Strategyproof approximation mechanisms for location on networks.

Abstract:
We consider the problem of locating a facility on a network, represented by
a graph. A set of strategic agents have different ideal locations for the
facility; the cost of an agent is the distance between its ideal location
and the facility. A \emph{mechanism} maps the locations reported by the
agents to the location of the facility. Specifically, we are interested in
social choice mechanisms that do not utilize payments. We wish to design
mechanisms that are \emph{strategyproof}, in the sense that agents can never
benefit by lying, or, even better, \emph{group strategyproof}, in the sense
that a coalition of agents cannot all benefit by lying. At the same time,
our mechanisms must provide a small approximation ratio with respect to one
of two optimization targets: the social cost or the maximum cost.
 
We give an almost complete characterization of the feasible truthful
approximation ratio under both target functions, deterministic and
randomized mechanisms, and with respect to different network topologies. Our
main results are: We show that a simple randomized mechanism is group
strategyproof and gives a $(2-2/n)$-approximation for the social cost, where
$n$ is the number of agents, when the network is a circle (known as a
\emph{ring} in the case of computer networks); we design a novel ``hybrid''
strategyproof randomized mechanism that provides a tight approximation ratio
of 3/2 for the maximum cost when the network is a circle; and we show that
no randomized SP mechanism can provide an approximation ratio better than
$2-o(1)$ to the maximum cost even when the network is a tree, thereby
matching a trivial upper bound of two.
 
Joint work with Noga Alon, Ariel Procaccia and Moshe Tennenholtz.

---

Speaker: Omer Tamuz, Weizmann Institute
Title: Truthful Cake Cutting 

Abstract: 
We address the problem of fair division, or cake cutting, with the
goal of finding truthful mechanisms. In the case of a general measure
space ("cake") and non-atomic, additive individual preference measures
- or utilities - we show that there exists a truthful "mechanism"
which ensures that each of the k players gets at least 1/k of the
cake. This mechanism also minimizes risk for truthful
players. Furthermore, in the case where there exist at least two
different measures we present a different truthful mechanism which
ensures that each of the players gets more than 1/k of the cake. This
mechanism is randomized, and we show that the same guarantees cannot
be achieved with a deterministic mechanism.

Joint work with E. Mossel.

---

Speaker: Uriel Feige,  Weizmann Institute of Science
Title: Responsive lotteries.

Abstract:
Given a set of alternatives and a single player, we introduce the
notion of a responsive lottery. These mechanisms receive as input from
the player a reported utility function, specifying a value for each
one of the alternatives, and use a lottery to produce as output a
probability distribution over the alternatives. Thereafter, exactly
one alternative wins (is given to the player) with the respective
probability. Assuming that the player is not indifferent to which of
the alternatives wins, a lottery rule is called truthful dominant iff
reporting his true utility function (up to affine transformations) is
the unique report that maximizes the expected payoff for the
player. We design truthful dominant responsive lotteries. We also
discuss their relations with scoring rules and with VCG mechanisms.

Joint work with Moshe Tennenholtz





*************************************
*** MONDAY (sublinear algorithms) ***
*************************************

Speaker: Gilad Tsur, Tel Aviv University
Title: Testing Properties of Sparse Images

Abstract:
We initiate the study of testing properties of images that correspond
to {\em sparse\/} $0/1$-valued matrices of size $n\times n$. Our study
is related to but different from the study initiated by Raskhodnikova
({\em Proceedings of RANDOM, 2003\/}), where the images correspond to
{\em dense\/} $0/1$-valued matrices. Specifically, while distance
between images in the model studied by Raskhodnikova is the fraction
of entries on which the images differ taken with respect to all $n^2$
entries, the distance measure in our model is defined by the fraction
of such entries taken with respect to the actual number of $1$'s in
the matrix. We study several natural properties: connectivity,
convexity, monotonicity, and being a line. In all cases we give
testing algorithms with sublinear complexity, and in some of the cases
we also provide corresponding lower bounds.

Joint work with Dana Ron.

---

Speaker: Lee-Ad Gottlieb, Hebrew University of Jerusalem
Title: Fast, precise and dynamic distance queries

Abstract:
We present an approximate distance oracle for a point set S with n
points and doubling dimension d. For every eps>0, the oracle supports
(1+eps)-approximate distance queries in (universal) constant time,
occupies space [eps^-O(d) + 2^O(d log d)]n, and can be constructed in
[2^O(d) log3 n + eps^-O(d) + 2^O(d log d)}]n expected time. This
improves upon the best previously known constructions, presented by
Har-Peled and Mendel. Furthermore, the oracle can be made fully
dynamic; This is the first fully dynamic (1+eps)-distance oracle.

Joint work with Yair Bartal, Liam Roditty, Moshe Lewenstein and Tsvi Kopelowitz

---

Speaker: Moni Naor, Weizmann Institute of Science
Title: Sketching in Adversarial Environments or Streaming Algorithms in Privacy and Security 

Abstract:
I will describe some instances of streaming algorithms in the context
of privacy and security. Most of the talk will concentrate on the
adversarial sketch model, that unifies the well-studied sketch and
data stream models together with a cryptographic flavor that considers
the execution of protocols in “hostile environments”, and provides a
framework for studying the complexity of many tasks involving massive
data sets.

In the adversarial sketch model several parties are interested in
computing a joint function in the presence of an adversary that
dynamically chooses their inputs. These inputs are provided to the
parties in an on-line manner, and each party incrementally updates a
compressed sketch of its input. The parties are not allowed to
communicate, they do not share any secret information, and any public
information they share is known to the adversary in advance. Then, the
parties engage in a protocol in order to evaluate the function on
their current inputs using only the compressed sketches.

The main technical contribution is an explicit and deterministic
encoding scheme that enjoys two seemingly conflicting properties:
incrementality and high distance.

Joint work with Ilya Mironov and Gil Segev.

---

Speaker: Artur Czumaj, University of Warwick
Title: Testing properties in arbitrary planar graphs via random walks

Abstract:
We study the testability of hereditary properties in arbitrary planar graphs.
Our main result is a constant time testing of bipartiteness in arbitrary planar
graphs. The previous bound for this class of graphs was $O^{\ast}(\sqrt{n})$,
and the constant-time testability was only known for planar graphs with {\bf
bounded degree}. Previously used transformations of unbounded-degree sparse
graphs into bounded-degree sparse graphs cannot be used to reduce the problem
to the testability of bounded-degree planar graphs. Our approach extends to
arbitrary minor-free graphs.

Our algorithm is based on random walks. The challenge here is to analyze random
walks for a class of graphs that has good separators, i.e., bad expansion.
Standard techniques that use a fast convergence to a uniform distribution do
not work in this case. Informally, our analysis technique self-reduces the
problem of finding an odd length cycle in a multigraph $G$ induced by a
collection of cycles to another multigraph $G'$ induced by a set of shorter
odd-length cycles, in such a way that when a random walks finds a cycle in $G'$
with probability p, then it does so with probability $f(p)$ in $G$. This
reduction is applied until the cycles collapse to selfloops that can be easily
detected.

Joint work with Morteza Monemizadeh, Krzysztof Onak, and Christian Sohler.




***************
*** TUESDAY ***
***************

Speaker: Mike Paterson, University of Warwick
Title: Overhang

Abstract:
Nearly everyone, we expect, is familiar with the classic problem of
arranging a stack of n rectangular blocks at the edge of a tabletop so
as to maximize the furthest overhang reached beyond the edge. The
classic solution achieves about 1/2 ln n times the length of a block
but assumes that each block rests on at most one other block. Without
this limitation a much more interesting problem emerges. A recent
paper by Uri Zwick and me showed an exponential improvement on the
classic solution and a more recent paper by Yuval Peres, Mikkel Thorup
and Peter Winkler together with us proved the best bound to within a
constant factor. These papers have appeared in the American
Mathematical Monthly.

I will present an overview of the construction and the matching bound,
and will give technical details of any of this depending on the wishes
and prior exposure to these results of the audience.





**************************************
*** WEDNESDAY (network algorithms) ***
**************************************

Speaker: Michael Dinitz, Weizmann Institute of Science.
Title: Directed Spanners via Flow-Based Linear Programs.

Abstract:
We examine directed spanners through flow-based linear programming
relaxations. We design an $\~O(n^{2/3})$-approximation algorithm for
the directed $k$-spanner problem that works for all $k\geq 1$, which
is the first sublinear approximation for arbitrary edge-lengths. Even
in the more restricted setting of unit edge-lengths, our algorithm
improves over the previous $\~O(n^{1-1/k})$ approximation of
Bhattacharyya et al. when $k\ge 4$. For the special case of $k=3$ we
design a different algorithm achieving an
$\~O(\sqrt{n})$-approximation, improving the previous
$\~O(n^{2/3})$. Both of our algorithms easily extend to the
fault-tolerant setting, which has recently attracted attention but not
from an approximation viewpoint. We also prove a nearly matching
integrality gap of $\Omega(n^{\frac13 - \epsilon})$ for any constant
$\epsilon > 0$.

A virtue of all our algorithms is that they are relatively
simple. Technically, we introduce a new yet natural flow-based
relaxation, and show how to approximately solve it even when its size
is not polynomial. The main challenge is to design a rounding scheme
that "coordinates" the choices of flow-paths between the many demand
pairs while using few edges overall. We achieve this, roughly
speaking, by randomization at the level of vertices.

Joint work with Robert Krauthgamer.

---

Speaker: Roy Schwartz, Technion.
Title: Balanced Graph Partitioning.
 
Abstract:
We consider the {\em $k$-partitioning} problem, where the goal is to
partition the vertices of an input graph $G$ into $k$ equally sized
components. We examine two objective functions.  The first is to
minimize the total weight of edges connecting different components
(min-sum objective). The second is to minimize the largest total
weight of edges that touch a single component (min-max
objective). Both objective functions are natural generalizations of
well-known graph partitioning problems, including {\em minimum
bisection} and {\em minimum balanced cut}.

For the min-sum case we provide a bicriteria approximation of
$O(\sqrt{\log{n}\log{k}})$ and for the min-max case we provide a
bicriteria approximation of $O(\sqrt{\log{n}}\log^{3/2}k)$. The
approximation algorithms for these two cases use different
approaches. In the min-sum case, spreading $\ell_2^2$ metrics are
rounded to obtain an approximate integral solution. However, in the
min-max case, a more combinatorial high level approach is needed. A
main tool in the algorithm for the min-max case is a new approximation
algorithm for the {\em $\rho$-unbalanced-cut} problem, where given a
graph $G=(V,E)$ the goal is to find a set $S\subseteq V$, $|S|=\rho
|V|$, that minimizes $\delta (S)$. We provide a bicriteria
approximation of $O(\sqrt{\log{n}\log{1/\rho}})$ for this
problem. Note that the special case of $\rho =1/2$ is the minimum
bisection problem, thus our bound extends that of ARV.

Joint work with: Nikhil Bansal, Robert Krauthgamer, Konstantin
Makarychev, Viswanath Nagarajan and Joseph (Seffi) Naor.

---

Speaker: Oren Weimann, Weizmann Institute of Science
Title: The replacement paths problem

Abstract:
Let G = (V,E) be a directed edge-weighted graph and let P be a
shortest path from s to t in G. The "replacement paths" problem asks
to compute, for every edge e on P, the shortest s-to-t path that
avoids e. Apart from approximation algorithms and algorithms for
special graph classes, the naive solution to this problem -- removing
each edge e on P one at a time and computing the shortest s-to-t path
each time -- was surprisingly the only known solution for directed
weighted graphs, even when the weights are integrals. In particular,
although the related shortest paths problem has benefited from fast
matrix multiplication, the replacement paths problem has not, and
still required cubic time.

For an n-vertex graph with integral edge-lengths in {-M,...,M}, I will
describe an O(Mn^{2.584}) time algorithm that uses fast matrix
multiplication and is sub-cubic for appropriate values of M. I will
also show how to construct a "distance sensitivity oracle" in the same
time bounds. A query (u,v,e) to this oracle requires sub-quadratic
time and returns the length of the shortest u-to-v path that avoids
the edge e. If time permits I will briefly describe an O(n log^2n)
time algorithm for solving the replacement paths problem when the
graph is planar.

Joint work with Raphy Yuster

---

Speaker: Matthias Englert, University of Warwick
Title: Almost Tight Bounds for Reordering Buffer Management

Abstract:
In the reordering buffer management problem a stream of colored items
arrives at a service station and has to be processed. The cost for
servicing the items heavily depends on the processing order: servicing
an item with color $c$, when the most recently serviced item had color
$c'\neq c$, incurs a context switching cost $w_c$. In order to reduce
the total processing cost, the service station is equipped with a
reordering buffer able to store $k$ items. This buffer can be used to
reorder the input sequence in a restricted fashion to construct an
output sequence with lower processing cost. At each point in time, the
buffer contains the first $k$ items of the input sequence that have
not yet been processed. A scheduling strategy has to decide which item
to service next. Upon its decision, the corresponding item is removed
from the buffer and serviced, while the next item from the input
sequence takes its place in the buffer. This simple and versatile
framework has many important applications in areas like production
engineering, computer graphics, storage systems, and information
retrieval, among others.

Our results are as follows: We present the first non-trivial lower
bounds on the competitive ratio of online algorithms. Specifically, we
show that any deterministic online algorithm for the reordering buffer
management problem has a competitive ratio of at least
$\Omega(\sqrt{\log k/\log\log k})$, even in the uniform case when
$w_c=1$ for all colors $c$. Next, we complement this lower bound by
presenting a deterministic online algorithm for the reordering buffer
management problem that obtains a competitive ratio of $O(\sqrt{\log
k})$, almost matching the lower bound. This improves upon a recent
algorithm by Avigdor-Elgrabli and Rabani (SODA 2010) which achieves a
competitive ratio of $O(\log k/\log\log k)$. Finally, we show a lower
bound of $\Omega(\log\log k)$ on the competitive ratio of any
\emph{randomized} online algorithm. In particular, our work provides
the first proof that no online algorithm (either deterministic or
randomized) for the reordering buffer management problem can achieve a
constant competitive ratio.

Joint work with Anna Adamaszek, Artur Czumaj, and Harald Räcke.

---

Speaker: Shiri Chechik, Weizmann Institute of Science
Title: Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension

Abstract:
tba.

---

Speaker: Merav Parter, Weizmann Institute of Science
Title: Distributed Power Control in the SINR Model

Abstract: 
The power control problem for wireless networks in the SINR model
requires determining the optimal power assignment for a set of
communication requests such that the SINR threshold is met for all
receivers. If the network topology is known to all participants, then
it is possible to compute an optimal power assignment in polynomial
time. In realistic environments, however, such global knowledge is
usually not available to every node. In addition, protocols that are
based on global computation cannot support mobility and hardly adapt
when participants dynamically join or leave the system. In this paper
we present and analyze a fully distributed power control protocol that
is based on \emph{local} information. For a set of communication
pairs, each consisting of a sender node and a designated receiver
node, the algorithm enables the nodes to converge to the optimal power
assignment (if there is one under the given constraints) quickly with
high probability. Two types of bounded resources are
considered,namely, the maximal transmission energy and the maximum
distance between any sender and receiver. It is shown that the
restriction to local computation increases the convergence rate by
only a multiplicative factor of $O(\log n+ \log \log \Psi_{\max})$,
where $\Psi_{\max}$ is the maximal power constraint of the network. If
the diameter of the network is bounded by $L_{\max}$ then the increase
in convergence rate is given by $O(\log n+ \log \log L_{\max})$.


This is joint work with Zvi Lotker, David Peleg and Yvonne Anne Pignolet.





*********************************************
*** THURSDAY (random discrete structures) ***
*********************************************

Speaker: Amin Coja-Oghlan, University of Warwick
Title: Phase transitions and computational complexity

Abstract:
Phase transitions have long been studied in statistical mechanics in the
context of disordered systems such as spin glasses. Indeed, physicists have
developed ingenious, albeit non-rigorous, techniques for the study of phase
transitions. In recent years it has emerged that phase transitions also play a
key role in computer science. In this talk I am going to give an overview of
this exciting area, and explain how ideas from statistical mechanics shed light
on the mystery of computational complexity. In addition, I am going to survey
the recent progress in turning the statistical mechanics work into a rigorous
theory.

---

Speaker: Michael Krivelevich, Tel Aviv University
Title: Packing Hamilton cycles in random and pseudo-random hypergraphs

Abstract:
We say that a k-uniform hypergraph C is a Hamilton cycle of type l,
for some 1<=l<=k, if there exists a cyclic ordering of the vertices
of C such that that every edge consists of k consecutive vertices
and for every pair of consecutive edges E_{i-1},E_i in C we have
|E_{i-1}-E_{i}|=l. (For the case k=2, we recover the usual
definition of a Hamilton cycle in a graph for l=1, while l=2
corresponds to a graph perfect matching.)

We prove that for every k>=2 and l<=k<2l, almost all edges of
a (relatively) dense random or pseudo-random k-uniform hypergraph
H on n vertices can be packed into edge-disjoint Hamilton cycles,
provided l divides n. A similar result is obtained for the (more
challenging) case of k=3,l=1.

Based on joint works with Alan Frieze and with Alan Frieze and
Po-Shen Loh.

---

Speaker: Elchanan Mossel, Weizmann Institute of Science
Title: Correlation and Agreement on randomness

Abstract:
tba.

---