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

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.

Details and abstract will be added when available.

Title:

Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond.

Abstract:

We consider the problem of estimating the size of a maximum matching when the edges are revealed in a streaming fashion. Consider a graph G=(V,E) with n vertices and m edges. The input stream is a permutation of edges S= (e_1,…,e_m) chosen by an adversary.

The goal is to output an estimation of the size of a maximum matching. The algorithm is only allowed to use a small amount of memory (much smaller than n).

When the underlying graph is planar, we present a simple and elegant streaming algorithm that with high probability estimates the size of a maximum matching within a constant factor using O-tilde(n^(2/3)) space. The approach generalizes to the family of graphs that have bounded arboricity. Graphs with bounded arboricity include, among other families of graphs, graphs with an excluded constant-size minor. To the best of our knowledge, this is the first result for estimating the size of a maximum matching in the adversarial-order streaming model (as opposed to the random-order streaming model). We circumvent the barriers inherent in the adversarial-order model by exploiting several structural properties of planar graphs, and more generally, graphs with bounded arboricity. We hope that this approach finds applications in estimating other properties of graphs in the adversarial-order streaming model. We further reduce the required memory size to O-tilde(sqrt(n)) for three restricted settings: (i) when the underlying graph is a forest; (ii) when we have 2-passes over the stream of edges of a graph with bounded arboricity; and (iii) when the edges arrive in random order and the underlying graph has bounded arboricity.

Finally, by introducing a communication complexity problem, we show that the approximation factor of a deterministic algorithm cannot be better than a constant using o(n) space, even if the underlying graph is a collection of paths. We can show that under a plausible conjecture for the hardness of the communication complexity problem, randomized algorithms with o(sqrt(n)) space cannot have an approximation factor better than a fixed constant.

Details and abstract will be added when available.

Speaker: Sofya Raskhodnikova

Abstract:

How quickly can we determine if an object satisfies some basic geometric property? For example, is the object a half-plane? Is it convex? Is it connected? If we need to answer such a question exactly, it requires at least as much time as it takes to read the object. In this talk, we will focus on approximate versions of these questions and will discuss how to solve them in time that depends only on the approximation parameter, but not the size of the input.

Specifically, an algorithm is given access to a discretized image represented by an n x n matrix of 0/1 pixel values. Another input to the algorithm is an approximation parameter, epsilon. The algorithm is required to accept images with the desired property and reject (with high probability) images that are far from having the desired property. An image is far if at least an epsilon fraction of its pixels has to be changed to get an image with the required property. For example, in this model, if the algorithm is allowed to read pixels of its choice, the half-plane property and convexity can be tested in time O(1/epsilon). If the algorithm receives access to pixels chosen uniformly and independently at random, then the half-plane property still takes O(1/epsilon) time, but for convexity the (optimal) bound on the running time is O(1/epsilon^(4/3)).

Based on joint work with Piotr Berman and Meiram Murzabulatov.

—

Title: Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension

Speaker: Gal Shahaf

Affiliation: The Hebrew University of Jerusalem

Abstract:

Algorithmic mechanism design (AMD) studies the delicate interplay between computational efficiency, truthfulness, and economic optimality. We focus on AMD’s paradigmatic problem: combinatorial auctions, and present new inapproximability results for truthful mechanisms in this scenario. Our main technique is a generalization of the classical VC dimension and the corresponding Sauer-Shelah Lemma.

Joint work with Amit Daniely and Michael Schapira

The talk is designed to be accessible to M.Sc. students, and includes an elementary introduction to VC dimension, combinatorial auctions and VCG mechanisms.

SPEAKER: Ilya Razenshteyn (MIT)

TITLE: Sketching and Embedding are Equivalent for Norms

__ABSTRACT: Imagine the following communication task. Alice and Bob each have a point from a metric space. They want to transmit a few bits and decide whether their points are close to each other or are far apart. Of particular interest are sketching protocols: Alice and Bob both compute short summaries of their inputs and then a referee, given these summaries, makes the decision; sketches are very useful for the nearest neighbor search, streaming, randomized linear algebra etc. Indyk (FOCS 2000) showed that for the l_p spaces with 0 < p <= 2 the above problem allows a very efficient sketching protocol. Consequently, any metric that can be mapped into the l_p space with all the distances being approximately preserved has a good protocol as well.____ __

I will show that for normed spaces (a very important class of metric spaces) embedding into l_p is the only possible technique for solving the communication problem. Slightly more formally, we show that any normed space that admits a good communication (in particular, sketching) protocol for distinguishing close and far pairs of points embeds well into l_p with p being close to 1. The proof uses tools from communication complexity and functional analysis.

__ As a corollary, we will show communication lower bounds for the planar Earth Mover’s Distance (minimum-cost matching metric) and for the trace norm (the sum of the singular values of a matrix) by deriving them from the (known) non-embeddability theorems and (the contrapositive of) our result.__

__ __

The talk is based on a joint paper with Alexandr Andoni and Robert Krauthgamer (arXiv:1411.2577).