Abstract: We study stable marriage and roommates problems in graphs with locality constraints. Each player is a node in a social network and has an incentive to match with other players. The value of a match is specified by an edge weight. Players explore possible matches only based on their current neighborhood. We study convergence of natural better response dynamics that converge to locally stable matchings -- matchings that allow no incentive to deviate with respect to their imposed information structure in the social network. For every starting state we construct in polynomial time a sequence of polynomially many better response moves to a locally stable matching. However, for a large class of oblivious dynamics including random and concurrent better response the convergence time turns out to be exponential. Perhaps surprisingly, convergence time becomes polynomial if we allow the players to have a small amount of random memory, even for many-to-many matchings and more general notions of neighborhood.

Abstract: In this paper, we study linear programming based approaches to the maximum matching problem in the semi-streaming model. The semi-streaming model has gained attention as a model for processing massive graphs as the importance of such graphs has increased. This is a model where edges are streamed-in in an adversarial order and we are allowed a space proportional to the number of vertices in a graph. In recent years, there has been several new results in this semi-streaming model. However broad techniques such as linear programming have not been adapted to this model. We present several techniques to adapt and optimize linear programming based approaches in the semi-streaming model with an application to the maximum matching problem. As a consequence, we (almost) improve all previous results on this problem, and also prove new results on interesting variants.

Abstract: We study the convergence time required to achieve consensus in dynamic networks. In each time step, a node's value is updated to some weighted average of its neighbors' and its old values. We study the case when the underlying network is dynamic, and investigate different averaging models. Both our analysis and experiments show that dynamic networks exhibit fast convergence behavior, even under very mild connectivity assumptions.

Abstract: This paper considers compact fault-tolerant routing schemes for weighted general graphs, namely, routing schemes that avoid a set of failed (or {\em forbidden}) edges. We present a compact routing scheme capable of handling multiple edge failures. Assume a source node $s$ contains a message $M$ designated to a destination target $t$ and assume a set $F$ of edges crashes (unknown to $s$). Our scheme routes the message to $t$ (provided that $s$ and $t$ are still connected in $G \setminus F$) over a path whose length is proportional to the distance between $s$ and $t$ in $G \setminus F$, the number of failures in $F$ and some poly-log factor. The routing table required at a node $v$ is of size proportional to the degree of $v$ in $G$ and some poly-log factor. This improves on the previously known fault-tolerant compact routing scheme for general graphs, which was capable of overcoming at most 2 edge failures.

Abstract: We study the problem of navigating through a database of similar objects using comparisons under heterogeneous demand, a problem strongly related to small-world network design. We show that, under heterogeneous demand, the small-world network design problem is NP-hard. Given the above negative result, we propose a novel mechanism for small-world network design and provide an upper bound on its performance under heterogeneous demand. The above mechanism has a natural equivalent in the context of content search through comparisons, again under heterogeneous demand; we use this to establish both upper and lower bounds on content-search through comparisons.

Abstract: We present new distributed deterministic solutions to two  communication problems in $n$-node ad-hoc radio networks: rumor gathering and multi-broadcast. In these problems, some or all nodes of the network initially contain input data called rumors,  which have to be learned by other nodes. In rumor gathering, there are $k$ rumors initially distributed arbitrarily among the nodes,  and the goal is to collect all the rumors at one node. Multi-broadcast is related to two fundamental communication problems: gossiping and routing. In gossiping, every node is initialized with a rumor and the goal is for all nodes to learn all rumors. In routing,  $k$ rumors distributed arbitrarily among the nodes must be delivered each to its designated destination. The problem of multi-broadcast, considered in this work, is a generalization of gossiping and a strengthening of routing, and is defined as follows: some $k$ rumors are distributed arbitrarily among the nodes and the goal is for all the nodes to learn every rumor. Our rumor gathering algorithm works in $O((k+n)\log n)$  time and our multi-broadcast algorithm works in $O(k\log^3 n+n\log^4 n)$~time,  for any $n$-node networks and $k$ rumors (with arbitrary $k$), which is a substantial improvement over the best previously known deterministic solutions to these problems. As a consequence, we \emph{exponentially} decrease  the gap between upper and lower bounds on the deterministic time complexity of four communication problems: rumor gathering, multi-broadcast, gossiping and routing,  in the important case when every node has initially at most one rumor (this is the scenario for gossiping and for the usual formulation of  routing). Indeed,  for $k=O(n)$, our results simultaneously decrease the complexity gaps for these four problems from polynomial to polylogarithmic in the size of the graph. Moreover, our {\em deterministic} gathering algorithm applied for  $k=O(n)$ rumors,  improves over the best previously known {\em randomized} algorithm of time $O(k\log n+ n\log^2 n)$.

Abstract: We study the problem of exploring an unknown undirected connected graph. Beginning in some start vertex, a searcher must visit each node of the graph by traversing edges. Upon visiting a vertex for the first time, the searcher learns all incident edges and their respective traversal costs. The goal is to find a tour of minimum total cost. Kalyanasundaram and Pruhs proposed a sophisticated generalization of a Depth First Search that is 16-competitive on planar graphs.  While the algorithm is feasible on arbitrary graphs, the question whether it has constant competitive ratio in general has remained open. Our main result is an involved lower bound construction that answers this question negatively. On the positive side, we prove that the algorithm has constant competitive ratio on any class of graphs with bounded genus.  Furthermore, we provide a constant competitive algorithm for general graphs with a bounded number of distinct weights.

Abstract: Suppose a client, Alice, has outsourced her data to an external storage provider, Bob, because he has capacity for her massive data set, of size $n$, whereas her private storage is much smaller---say, of size $O(n^{1/r})$, for some constant $r>1$. Alice trusts Bob to maintain her data, but she would like to keep its contents private. She can encrypt her data, of course, but she also wishes to keep her access patterns hidden from Bob as well. In this paper, we describe a scheme for this \emph{oblivious RAM simulation} problem with a small logarithmic or polylogarithmic amortized increase in her access times, while keeping the storage Alice purchases from Bob to be of size $O(n)$.   To achieve this, our algorithmic contributions include a parallel MapReduce cuckoo-hashing algorithm and an external-memory data-oblivious sorting algorithm.

Abstract: We investigate how collusion affects the social cost in atomic splittable routing games. Suppose that players form coalitions and each coalition behaves as if it were a single player controlling all the flows of its participants. It may be tempting to conjecture that the social cost would be lower after collusion, since there would be more coordination among the players. We construct examples to show that this conjecture is not true. Even in very simple single-source-single-destination networks, the social cost of the post-collusion equilibrium can be higher than that of the pre-collusion equilibrium. This counter-intuitive phenomenon of collusion prompts us to ask the question: \emph{under what conditions would the social cost of the post-collusion equilibrium be  bounded by the social cost of the pre-collusion equilibrium?} We show that if (i) the network is ``well-designed'' (satisfying a natural condition), and  (ii) the delay functions are affine, then collusion is always beneficial for the social cost in the Nash equilibria. On the other hand, if either of the above conditions is unsatisfied, collusion can worsen the social cost. Our main technique is a novel flow-augmenting algorithm to build Nash equilibria. Our positive result for collusion is obtained by applying this algorithm simultaneously to two different flow value profiles of players and observing the difference in the derivatives of their social costs. Moreover, for a non-trivial subclass of selfish routing games, this algorithm finds the \emph{exact} Nash equilibrium in polynomial time.

Abstract: We study the wireless scheduling problem in the physically realistic SINR model. More specifically: we are given a set of $n$ links, each a sender-receiver pair.  We would like to schedule the links using the minimum number of slots, given the SINR model of interference among simultaneously transmitting links.  In the basic problem, all senders transmit with the same uniform power. In this work, we provide a distributed $O(\log n)$-approximation for the scheduling problem, matching the best ratio known for centralized algorithms.  This is based on an algorithm of Kesselheim and V\"ocking, improving their analysis by a logarithmic factor.  We show this to be best possible for any such distributed algorithm. Our analysis extends also to linear power assignments, and as well as for more general assignments, modulo assumptions about message acknowledgement mechanisms.

Abstract: We propose a new protocol solving the fundamental problem of disseminating a piece of information to all members of a group of $n$ players. It builds upon the classical randomized rumor spreading protocol and several extensions. The main achievements are the following: Our protocol spreads a rumor from one node to all other nodes in the asymptotically optimal time of $(1 + o(1)) \log_2 n$. The whole process can be implemented in a way such that only $O(n f(n))$ calls are made, where $f(n)= \omega(1)$ can be arbitrary. In spite of these quantities being close to the theoretical optima, the protocol remains relatively robust against failures. We show that for \emph{random} node failures, our algorithm again comes arbitrarily close to the theoretical optima. The protocol can be extended to also deal with \emph{adversarial} node failures. The price for this additional robustness is only a constant factor increase in the run-time, where the constant factor depends on the fraction of failing nodes the protocol is supposed to cope with. It can easily be implemented such that only $O(n)$ calls to properly working nodes are made. In contrast to the push-pull protocol by Karp et al. [FOCS 2000], our algorithm only uses push operations, i.e., only informed nodes take active actions in the network. To the best of our knowledge, this is the first randomized push algorithm that achieves an asymptotically optimal running time.

Abstract: Given a graph G = (V,E) with non-negative edge-lengths whose vertices are assigned a label from L = {\lambda_1,...,\lambda_\ell}, we construct a compact distance oracle that answers queries of the form: "What is d(v,\lambda)?", where v is a vertex in the graph, \lambda a vertex-label, and d(v,\lambda) is the distance (length of the shortest path) between v and the closest vertex labeled \lambda in G. We give the first formalization of this natural problem and provide a hierarchy of approximate distance oracles that require subquadratic space, and return a distance of constant-stretch.We also extend our solution to dynamic oracles that can handle label changes in sublinear time.

Abstract: Given a set of $n$ mobile robots in the d-dimensional Euclidean space, the goal is to let them converge to a single not predefined point. The challenge is that the robots are limited in their capabilities. We consider the well-studied family of robotic capabilities where a robot can, upon activation, compute the positions of all other robots using an individual affine coordinate system. The robots are indistinguishable, oblivious and may have different affine coordinate systems, which may even change over time. A very general discrete time model assumes that robots are activated in arbitrary order. Further, the computation of a new target point may happen much earlier than the movement so that the movement is based on outdated information about other robot's positions. Time is measured as the number of rounds, where a round ends as soon as each robot has moved at least once. In [CP05], the Center of Gravity is considered as target function. This target function is invariant against the choice of the affine coordinate system. Convergence is proven, and the number of rounds needed for halving the diameter of the convex hull of the robot's positions is shown to be O(n^2) and Omega(n). In this paper, we present an easy-to-check property of target functions that guarantees convergence and yields upper time bounds. This property intuitively says that when a robot computes a new target point, this point is significantly within the current axis-aligned minimal box containing all robots. (Note that this box is defined relative to a fixed coordinate system and cannot be computed by the robots.) This property holds, for example, for the above-mentioned target function, and improves the above O(n^2) to an asymptotically optimal O(n) upper bound. Our technique also yields a constant time bound for a target function that requires that all robots have the same coordinate system.

Abstract: We study two (classes of) distributed algorithms for power control in a general model of wireless networks. There are n wireless communication requests or links that experience interference and noise. To be successful a link must satisfy an SINR constraint. The goal is to find a set of powers such that all links are successful simultaneously. A classic algorithm for this problem is the fixed-point iteration due to Foschini and Miljanic [1992], for which we prove the first bounds on worst-case running times -- after roughly O(n log n) rounds all SINR constraints are nearly satisfied. When we try to satisfy each constraint exactly, however, convergence time is infinite. For this case, we design a novel framework for power control using regret learning algorithms and iterative discretization. While the exact convergence times must rely on a variety of parameters, we show that roughly a polynomial number of rounds suffices to make every link successful during at least a constant fraction of all previous rounds.

Abstract: Congestion games model several interesting applications, including routing and network formation games, and also possess attractive theoretical properties, including the existence of and convergence of natural dynamics to a pure Nash equilibrium. Weighted variants of congestion games that rely on sharing costs proportional to players' weights do not generally have pure-strategy Nash equilibria. We propose a new way of assigning costs to players with weights in congestion games that recovers the important properties of the unweighted model. This method is derived from the Shapley value, and it always induces a game with a (weighted) potential function. For the special cases of weighted network cost-sharing and atomic selfish routing games (with Shapley value-based cost shares), we prove tight bounds on the price of stability and price of anarchy, respectively.

Abstract: Threshold cryptography aims at enhancing the availability and security of encryption and signature schemes by splitting private keys into several (say $n$) shares (typically, each of size comparable to the original secret key).  In these schemes, a quorum ($t \leq n$) of servers needs to act upon a message to produce the result (decrypted value or signature), while corrupting less than $t$ servers maintains the security of the scheme. For about two decades starting from the mid 80's, extensive study was dedicated to this subject, which created a number of notable results. So far, most practical threshold signatures, where servers act non-interactively, were analyzed in the limited static corruption  model (where the adversary chooses which servers will be corrupted at the system's initialization stage). Existing threshold encryption schemes that withstand the strongest combination of adaptive corruptions (allowing the adversary to corrupt servers at any time based on his complete view), and chosen-ciphertext attacks (CCA) all require interaction (in the non-idealized model) and attempts to remedy this problem resulted only in relaxed schemes. To date (and for about 10 years), it was an open problem whether there are non-interactive threshold schemes providing the highest security (namely, CCA-secure encryption and CMA-secure signature) with scalable shares (i.e., shares are as short as the original key) and adaptive security. This paper answers this question affirmatively by presenting such efficient encryption and signature schemes within a unified algebraic framework.

Abstract: Network flows that vary over time arise naturally when modeling rapidly evolving systems such as the Internet. In this paper, we continue the study of equilibria for flows over time in the deterministic queuing model proposed by Koch and Skutella. We give a constructive proof for the existence and uniqueness of equilibria for the case of a piecewise constant inflow rate, through a detailed analysis of the static flows obtained as derivatives of a dynamic equilibrium. We also provide a nonconstructive existence proof of equilibria when the inflow rate is a general function.