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

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).

Title: Nonconvex Statistical Optimization: Algorithm and Model-based Optimization Theory

Abstract: Nonconvex regularized M-estimators have been widely applied to high dimensional data analysis. Existing statisticaltheory has established their statistical properties

in high dimensions only when the global optimum or certain local optimum can be obtained. Though practitioners have proposed numerous heuristic computational algorithms for

solving these nonconvex optimization problems, existing optimization theory does not necessarily guarantee these algorithms to obtain the global or local optima with

desired statistical properties in polynomial time. Therefore, there exists a significant gap between theory and practice: What is actually computed is not the same as what has

been proved. To bridge this gap, we propose a new generation of nonconvex statistical optimization algorithms and model-based theory, which incorporate the statistical thinking

into modern optimization. When developing computational algorithms, we take underlying sparse statistical models into consideration. Particularly, for nonconvex regularized

M-estimation problems, our proposed algorithms devise three different optimization schemes, under which the solutions achieved by the optimization algorithm always falls within

a restricted sparse set. Thus the nonconvex objective function mimics the behavior of a strongly convex function, which eventually allows our proposed algorithms to obtain an

estimator with the desired optimal statistical properties in polynomial time with high probability

Speaker: Aravind Srinivasan

Affiliation: University of Maryland

Title: Properties and Generalizations of the Moser-Tardos Process

Abstract: Moser and Tardos have developed an elegant and powerful algorithmic version of the Lovasz Local Lemma. Since the publication of this work, it has become apparent that this algorithm has some very interesting properties and extensions, and can be viewed as a stochastic process of independent interest. I will survey some of these, especially the ideas of “partial resampling” and the “LLL-distribution” (the properties of the output distribution of Moser-Tardos). I will draw from joint works with Haeupler and Saha, with Harris, and with Chen and Harris.

Title: Fault Resilient Graph Structures

Speaker: Merav Parter (MIT)

Abstract:

A fault-tolerant (FT) structure for a network is required to continue functioning following the failure of some of the network’s edges or vertices. Fault-resilience can be introduced into the network in several different ways. This talk will focus on a notion of fault-tolerance whereby the structure at hand is augmented (by adding to it various components) so that subsequent to the failure of some of the network’s vertices or edges, the surviving part of the structure is still operational. As this augmentation carries certain costs, it is desirable to minimize the number of added components.We will revise several constructions of sparse fault tolerant structures such as FT spanner and FT shortest-path trees. I will also present a new model for fault resilient network structures that mix two orthogonal protection mechanisms: (a) backup, namely, augmenting the structure with many (redundant) low-cost and fault-prone components, and (b) reinforcement, namely, acquiring high-cost but fault-resistant components. A trade-off between these two mechanisms will be presented in a concrete setting of shortest-path trees.