We typically have seminars on Wednesday at noon in Malone 228. All seminar announcements will be sent to the theory mailing list.

Speaker: Michael Dinitz

Affiliation: Johns Hopkins University

Title: Approximating Graph Spanners

Abstract:

Graph spanners (subgraphs which approximately preserve distances) have been studied extensively since the 1980’s. Many of the known results are about the optimal tradeoffs between various parameters, particularly the stretch and size of the spanner. But there has been some recent progress on a different and less developed line of research: fixing the allowable stretch, and optimizing the size. This turns spanners into more of a computational problem, and allows us to use many of the standard techniques from approximation algorithms (convex relaxations in particular). In this talk we will give an overview of some of the progress in this area, its limitations, and some possible future directions.

Speaker: David Harris

Affiliation: University of Maryland – College Park

Title: Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lov\'{a}sz Local Lemma

Abstract: The Lopsided Lovasz Local Lemma (LLLL) is a powerful probabilistic principle which has been used in a variety of combinatorial constructions. While this principle began as a general statement about probability spaces, it has recently been transformed into a variety of polynomial-time algorithms. The resampling algorithm of Moser & Tardos is the most well-known example of this. A variety of criteria have been shown for the LLLL; the strongest possible criterion was shown by Shearer, and other criteria which are easier to use computationally have been shown by Bissacot et al, Pegden, and Kolipaka & Szegedy.

We show a new criterion for the Moser-Tardos algorithm to converge. This criterion is stronger than the LLLL criterion, and in fact can yield better results even than the full Shearer criterion. This is possible because it does not apply in the same generality as the original LLLL; yet, it is strong enough to cover many applications of the LLLL in combinatorics. We show a variety of new bounds and algorithms. A noteworthy application is for $k$-SAT, with bounded occurences of variables. As shown in Gebauer, Szabo, and Tardos, a $k$-SAT instance in which every variable appears $L \leq \frac{2^{k+1}}{e (k+1)}$ times, is satisfiable. Although this bound is asymptotically tight (in $k$), we improve it to $L \leq \frac{2^{k+1} (1 – 1/k)^k}{k-1} – \frac{2}{k}$ which can be significantly stronger when $k$ is small.

Speaker: Matthew Andrews

Affiliation: Alcatel-Lucent Bell Labs

Title: Understanding Sponsored Content in Mobile Data Networks

Abstract:

Sponsored content is a mechanism in which content providers can pay the operator of a wireless network to make their content free to end users. Such offerings have recently been introduced in both the US and Asia and they raise many challenging questions regarding which sites should be candidates for sponsoring and how much the service provider should charge the content provider.

In this talk we introduce a number of models that aim to capture the interactions between the service provider, the content provider and the end users in a sponsored content offering. We show that it is possible to design the system so that it is win-win-win for all players. In many settings the problem is a generalization of the “Adwords” problem that arises in the design of sponsored search. We also show how to analyze network traffic and content provider financial data in order to calculate the input parameters for these models.

Speaker: Jeremy Fineman

Affiliation: Georgetown University

Title:

How to Fix Exponential Backoff: Achieving Constant Throughput and Robustness with Polylog Attempts

Abstract:

Randomized exponential backoff is employed in many domains to coordinate access to a shared resource or communication channel. Despite the ubiquity of the protocol, exponential backoff has poor general performance guarantees. Most notably, exponential backoff neither achieves constant throughput in a general online setting, nor is it robust to corrupted or jammed messages. This talk considers a new backoff protocol that achieves constant throughput, even in the presence of an adaptive adversary that jams (or blocks access to) the shared resource at certain times. The protocol also makes relatively few attempts to access the resources, which means that each agent does not expend too much energy. Specifically, we show that the expected energy per agent is O(log^2(n+J)), where n is the number of contenders and J is the amount of time the adversary jams.

Speaker: Alex Slivkins

Affiliation: Microsoft Research – New York

Title: Bandits with Resource Constraints

Abstract:

Multi-armed bandits is the predominant theoretical model for exploration-exploitation tradeoff in machine learning, with countless applications ranging from medical trials, to communication networks, to Web search and advertising, to dynamic pricing. In many of these application domains the learner may be constrained by one or more supply/budget limits, in addition to the customary limitation on the time horizon. We introduce a general model that encompasses such problems, combining aspects of stochastic integer programming with online learning. A distinctive feature (and challenge) in our model, compared to the conventional bandit problems, is that the optimal policy for a given problem instance may significantly outperform the policy that always chooses the best fixed action. Our main result is an algorithm with near-optimal regret relative to the optimal policy. Also, we extend this result to contextual bandits, and detail an application to dynamic pricing.

Mohammad Hajiaghayi

University of Maryland – College Park

Title: Parameterized and Promised Streaming: Matching and Vertex Cover

Abstract:

As graphs continue to grow in size, we seek ways to effectively

process such data at scale. The model of streaming graph processing, in

which a compact summary is maintained as each edge insertion/deletion

is observed, is an attractive one. However, few results are known for

optimization (often NP-hard) problems over such dynamic graph streams.

In this talk, we introduce a new approach to handling graph streams,

by instead seeking solutions for the parameterized (and promised) versions of

these problems. Here, we are given a parameter k and the objective is to

decide whether there is a solution bounded by k. By combining

kernelization techniques with randomized sketch structures, we obtain the

first streaming algorithms for the parameterized versions of Maximal

Matching and Vertex Cover. We consider various models for a graph stream on n

nodes: the insertion-only model where the edges can only be added, and

the dynamic model where edges can be both inserted and deleted.

Gordon Wilfong

Alcatel-Lucent Bell Labs

Title: Optimal Path Encoding

Abstract: Packet networks need to maintain state in the form

of forwarding tables at each switch. The cost of this state

increases as networks support ever more sophisticated per-flow

routing, traffic engineering, and service chaining. Per-flow or per-path

state at the switches can be eliminated by encoding each

packet’s desired path in its header. A key component of such a

method is an efficient encoding of paths.

We introduce a mathematical formulation of this optimal path encoding

problem. We prove that the problem is APX-hard, by

showing that approximating it to within a factor less than 8/7

is NP-hard. We then present an algorithm

approximating the optimal path-encoding problem to within a

factor 2. Finally, we provide empirical results illustrating the

effectiveness of the proposed algorithm.

Joint work with A. Hari (Bell Labs) and U. Niesen (Qualcomm)

Speaker: Lisa Zhang

Affiliation: Alcatel-Lucent Bell Labs

Title: Analysis of k-Anonymity Algorithms for Streaming Location Data

Abstract:

We propose and analyze algorithms to achieve k-anonymity for streaming location data. We consider a framework motivated by European Union privacy requirements, in which location information arrives online into a buffer of fixed size m. Whenever the buffer fills, some data must move to permanent storage in a k-anonymized fashion. This notion of anonymity refers to recording a coarse common region containing at least k points instead of separate exact locations. One primary goal is to minimize the recorded region size so that the anonymized location data is as accurate as possible.

We observe that under competitive analysis, any online algorithm can be arbitrarily bad in terms of the recorded region size. We therefore assume a more benign model in which the location distribution is known. For a uniform distribution, we analyze a simple, natural algorithm that partitions the space into m/k identical regions to ensure k-anonymity, and picks the region with the largest occupancy whenever the buffer fills. Our detailed analysis shows

that the largest occupancy converges to 2k. This implies, perhaps somewhat unintuitively, that it is sufficient to achieve k-anonymity by partitioning space into $2m/k$ regions, which reduces and thereby improves the recorded region size by a factor of 2. We also present an almost matching lower bound of 2m/k. Finally, we discuss generalizations to nonuniform distributions by partitioning the space to match the given distribution.

Speaker: Sanjeev Khanna

Affiliation: University of Pennsylvania

Title: Tight Bounds for Linear Sketches of Approximate Matchings

Abstract:

We consider the problem of approximating a maximum matching in dynamic graph streams where the stream may include both edge insertions and deletions. Our main result is a resolution of the space complexity of linear sketches for approximating the maximum matching in this model.

Specifically, we show that for any $\eps > 0$, there exists a single-pass streaming algorithm, which only maintains a linear sketch of size roughly $n^{2-3\eps}$ bits and recovers an $n^\epsilon$-approximate maximum matching in dynamic graph streams, where $n$ is the number of vertices in the graph. We complement this result with the following lower bound result: any linear sketch for approximating the maximum matching to within a factor of $n^\eps$ has to be of size at least $n^{2-3\eps -o(1)}$ bits.

This is based on joint work with Sepehr Assadi, Yang Li, and Grigory Yaroslavtsev.