TOC Seminar Spring 2010

Feb 2

Madhu Sudan

Microsoft Research/MIT

Semantic Goal-Oriented Communication

For a few years now Brendan Juba and I have been exploring the notion of meaning of bits, and in particular, wondering if this can be communicated on a classical communication channel. Part of the challenge here is in defining ``meaning'' in the right way (to allow it to be communicated).

In our first work (STOC 2008) we asserted that the right way to associate meaning is look at why the communicating parties are doing it (what is their self interest in doing so). We describe a specific goal (one of the players is interested in solving some hard computational problem and the other player just wants to help) and showed that such a goal could be achieved in the presence of initial misunderstanding.

In recent work (joint with Brendan and Oded Goldreich (Weizmann)) we now extend our initial investigation to consider completely generic goals of communication and investigate when semantic communication is possible. We give a definition of a generic goal, explain what semantic misunderstanding is, and describe a concept called ``sensing'' which seems almost necessary/sufficient for semantic communication.

The talk will focus on the more recent work, but no knowledge of the prior work will be assumed.

Feb 10

Unusual day

1pm – 2pm

Unusual time

Room 32-G449

(Patil-Kiva)

Unusual place

Christos Papadimitriou

UC Berkeley

Computing Nash equilibria: The plot thickens

Myerson has argued that the Nash equilibrium lies at the foundations of modern economic thought, and yet the dark computational side of the concept keeps getting gloomier.   We show that playing games under considerations of risk, disambiguating games via equilibrium selection a’-la Harsanyi-Selten, and computing equilibria by thehomotopy method, are all rife with very serious complexity impediments.

Joint work with Paul Goldberg and Amos Fiat.

Feb 11

Unusual day

1:30pm – 2:30pm

Unusual time

Room 32-G449

(Patil-Kiva)

Unusual place

Leonid Gurvits

Los Alamos National Laboratory

A story of one convex relaxation, and of the related revelation

I’ll discuss remarkably short proofs of some inequalities for the permanent of an n-by-n matrix — including the celebratedpermanental Egorychev-Falikman and Schrijver Inequalities.  Many of these inequalities have applications to approximation algorithms for the permanent.  I’ll also discuss some recent generalizations. Graduate and undergraduate students are encouraged to attend: the stuff is beautifully simple.

Feb 16

No Colloquium in honor of

MIT Monday andCookiefest

Feb 25

Unusual day

1:30pm – 2:30pm

Unusual time

Room 32-D463

(Star-conference room)

Unusual place

Vitaly Feldman

IBM Almaden

On the statistical query complexity of learning monotone functions

Statistical query (SQ) learning model of Kearns (1993) is a natural restriction of the PAC learning model in which a learning algorithm is allowed to obtain estimates of statistical properties of the unknown function instead of the random examples. I will describe two results that address the complexity of learning in the SQ model. The first result is a new and simple characterization of the complexity of SQ learning and the second one is monotone hardness amplification for SQ learning based on O'Donnell's (2002) celebrated technique. I'll also demonstrate how these results can be used to derive the first unconditional lower bounds for SQ learning of monotone depth-3 and depth-4 formulas.

Parts of the talk are based on a joint work with Lee and Servedio.

Mar 2

Avinatan Hassidim

MIT

Implementing Mechanisms

A mechanism can be viewed as a function which maps the actions of the players (e.g. bids in an auction) to an outcome (e.g. who gets what goods) and to a vector of prices (how much each player pays). A basic question in mechanism design is that of implementability: "Suppose someone specifies the outcome for each set of inputs. Is there a pricing rule which will cause the players to be truthful?"

In the talk I will present an exact characterization of which functions are implementible and which are not. Time permitting, I will discuss two functions which cannot be implemented, and show how a weaker notion of implementation is relevant for them.

The talk is based on joint works with Itai Ashlagi, Mark Braverman, Jing Chen, Silvio Micali, Dov Monderer and Al Roth.

Mar 9

Nir Shavit

Tel-Aviv University

Hashing and the New Multicore Algorithmics

As multicore machines become our mainstream computing platform, their unique architectural properties (supporting synchronization and coherence) and the new classes of algorithms they are intended to run, are forcing us to rethink our basic algorithms. The result is a flurry of activity in the design of concurrent algorithms and techniques to improve concurrent programming.

This talk will provide a glimpse into the work in this area. I will use concurrent hashing as an example of this new research wave, presenting two new high performance multicore hash-table algorithms: split-ordered hashing and hopscotch hashing. These algorithms are examples of how the new hardware has necessitated alternative algorithmic approaches, and how in turn these newalgorithmics carry into the sequential world.

Mar 16

No Colloquium

Mar 23

No Colloquium

in honor of

Spring Break

Mar 30

Daron Acemoglu

MIT

Dynamic Coalition Formation

Many social situations can be modeled as games of coalition formation. For example, the allocation of resources in many environments are determined by a subset of the agents that forms a "sufficiently powerful" coalition; the membership and the rules of many clubs are determined by a coalition consisting of a subset of current members; a constitution is enacted  by a coalition of the voters that form a majority or supermajority. While these and many other situations can be analyzed as coalition formation games, static analyses miss an important dimension of the relevant interactions: real world resource allocation problems are often dynamic; the rules and membership of the club are determined for future periods; and constitutions are only relevant if they are stable and endure. In all of these examples, not only are interactions dynamic, but a central feature is that the rules that govern the procedures for future decision-making and the distribution of political power across players are determined by current decisions. For example, current constitutional change must take into account how the new constitution may pave the way for further changes in laws and regulations.

This talk will introduce different mathematical models of dynamic coalition formation. After presenting some examples, we outline a general framework for the analysis of a wide class of dynamic coalition formation problems. We define "states" as combinations of allocations of payoffs and future decision-making power (summarized by the set of coalitions that have the "power" the transition from one state to another). A state is dynamically stable if it emerges and persists in equilibrium. We show that, under relatively natural acyclicity assumptions, a complete and recursive characterization of dynamically stable states can be obtained. We also provide conditions for (essential) uniqueness of dynamically stable states. This characterization highlights two intuitive features of dynamic coalition formation: (1) a social arrangement (a state or coalition) is made stable by the instability of alternative arrangements that are preferred by sufficiently many members of the society; (2) efficiency-enhancing changes are often resisted because of further social changes that they will engender. We also show how the general framework can be applied in several different contexts.

Based on joint work with Georgy Egorov and Konstantin Sonin.

April 6

Avrim Blum

CMU

A new theoretical framework for clustering

Theoretical treatments of clustering have generally been of two types: either on algorithms for (approximately) optimizing various distance-based objectives such as k-median, k-means, min-sum, etc, or on clustering under probabilistic "generative model" assumptions such as mixtures of Gaussian or related distributions.

In this work we propose a new approach to analyzing the problem of clustering.  Building on models used in computational learning theory, we consider the goal of approximately recovering an unknown target clustering from given pairwise similarity or distance information, without making generative-model assumptions about the data.  Instead, we ask: what relations between the similarity/distance information and the desired clustering are sufficient to cluster well – these relations taking the role of the "concept class" in learning theory. Within this framework, we then present a number of interesting graph-theoretic and game-theoretic properties that we show are sufficient for an algorithm to succeed.

As one concrete application, we show that if our distances have the property that any 1.1-approximation to the k-median (or k-means or min-sum) objective would have error < epsilon wrt the target (an ostensible reason for *wanting* to approximate the objective to a 1.1 factor) then we can efficiently find a solution that is O(epsilon)-close to the target, even though achieving a 1.1 approximation to these objectives is NP-hard.  (One can replace 1.1 with 1+alpha for any constant alpha>0).  I will also mention some interesting extensions and open problems in this direction.

This talk is based on work joint with Maria-Florina Balcan, AnupamGupta, and Santosh Vempala.

April 13

Anna Lubiw

University of Waterloo

Simultaneous Graph Problems

We examine problems of representing two graphs that share some vertices and edges, with a "simultaneity" requirement that the common subgraph be represented the same way.  Such problems arise whenever it is desirable to consistently represent two related graphs, for example: graphs connected in time, where one is an updated version of the other; or two social networks that share some members; or overlap graphs of DNA fragments of two similar organisms.

Two graphs that share some vertices are *simultaneously planar* if they have planar embeddings with the common vertices and edges represented by the same points and curves.  We discuss what is known about this class.

Two graphs are *simultaneous interval graphs* if they can be represented as intersection graphs of intervals with common vertices represented by the same intervals.  We give a polynomial time recognition algorithm (joint work with K.R. Jampani).  This problem, and others dealing with simultaneous intersection graphs, is related to graph sandwich problems and to probe graphs.

April 20

Jakob Nordström

MIT

Understanding Space in Proof Complexity: Separations and Trade-offs

In recent years, deciding if a CNF formula is satisfiable has gone from a theoretical question to a practical approach for solving real-world problems. For current state-of-the-art satisfiability algorithms, typically based on resolution and clause learning, the two main bottlenecks are the amounts of time and memory space used. Understanding time and memory consumption of SAT-solvers, and how these resources are related to one another, is therefore a question of great interest.

Roughly a decade ago, it was asked whether proof complexity had anything intelligent to say about this question, corresponding to the interplay between size and space of proofs. In this talk, I will explain how this question can be answered almost completely by combining two tools, namely good old pebble games on graphs, studied extensively in the 70s and 80s, and a new, somewhat surprising, theorem showing how weak space lower bounds can be amplified to strong bounds simply by making variable substitutions in the corresponding CNF formulas.

Joint work with Eli Ben-Sasson.

April 27

David Staelin

MIT

Fast-learning neural models that maximize

Shannon information storage

The human brain surpasses our finest computers using only ~30 watts, millisecond switching speeds, and unreliable neurons that individually signal via isolated voltage spikes sent roughly every second to perhaps 10,000 other neurons.  We currently have no theoretical understanding of how this could work or what might constitute plausible performance bounds.  Moreover, Blum andRivest have shown that training even three canonical neurons in a classic reward-based fashion is arguably NP-complete, compounding our problem. Illustrative fundamental open theoretical questions include: 1) the proper definition of Shannon information in a neural context, 2) its practical upper bounds, and 3) identification of an explanatory neural model that permits these questions to be addressed with precision, even if biologically oversimplified.

A fast-learning neural model that can store perhaps 200 bytes will be presented along with suggestions of how such units might function collectively.  The multi-faceted similarity between optimized model characteristics and those of cortical neurons will be summarized briefly, followed by suggestions of theoretical questions about neural spike processing that may now become addressable.

Joint work with K. T. Herring and C. H. Staelin

May 4

David Steurer

Princeton

Subexponential Algorithms for Unique Games and Related Problems

We give a subexponential time approximation algorithm for the Unique Games problem: Given a Unique Games instance with alphabet size k such that a 1-epspilon^6 fraction of the constraints can be satisfied, our algorithm finds in time exp(k*n^epsilon) an assignment that satisfies a 1-epsilon fraction of the constraints.

We also obtain subexponential algorithms with similar approximation guarantees for Small-Set Expansion and Multi Cut.  For Max Cut, Sparsest Cut and Vertex Cover, our techniques lead to subexponentialalgorithms with improved approximation guarantees on subclasses of instances.

Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for Unique Games. While our result stops short of refuting the UGC, it does suggest that Unique Games is significantly easier than NP-hard problems such as Max 3-SAT, Label Cover and more, that are believed not to havesubexponential algorithms achieving a non-trivial approximation ratio.

The main component in our algorithms is a new kind of graph

decomposition that may have other applications: We show that by changing an epsilon fraction of its edges, any regular graph on n vertices can be broken into disjoint parts such that the stochastic adjacency matrix of each part has at most n^epsilon eigenvalues larger than 1-epsilon^6.

Joint work with Sanjeev Arora and Boaz Barak.

May 11

Jeffrey Shallit

University of Waterloo

(visiting MIT)

Open Problems in Automata Theory and Formal Languages

Automata theory and formal languages don't get any respect, but they should, because there are still many interesting and beautiful open problems to think about.  In this talk I will give a personal view of some of my favorite open problems from these fields. Probably some of them would succumb to a few hours of thought by a bright MIT student, so come and be prepared to solve them.