TOC COLLOQUIUM CALENDAR

Sept 15

Unusual Place: 32-124

Erik Demaine,

MIT

Algorithms Meet Art, Puzzles, and Magic

When I was six years old, my father Martin Demaine and I designed and made puzzles as the Erik and Dad Puzzle Company, which distributed to toy stores across Canada.  So began our journey into the interactions between algorithms and the arts (here, puzzle design).  More and more, we find that our mathematical research and artistic projects converge, with the artistic side inspiring the mathematical side and vice versa.  Mathematics itself is an art form, and through other media such as sculpture, puzzles, and magic, the beauty of mathematics can be brought to a wider audience. These artistic endeavors also provide us with deeper insights into the underlying mathematics, by providing physical realizations of objects under consideration, by pointing to interesting special cases and directions to explore, and by suggesting new problems to solve (such as the metapuzzle of how to solve a puzzle).  This talk will give several examples in each category, from how our first font design led to a universality result in hinged dissections, to how studying curved creases in origami led to sculptures at MoMA.  The audience will be expected to participate in some live magic demonstrations. 

Sept 22

Adam Kalai,

Microsoft Research New England

An Overview of Agnostic Learning

Agnostic Learning (Kearns, Schapire and Sellie '92; Haussler '90) is a computational model of learning in which little or no assumptions are made about the true function being learned. Consequently, agnostic learning algorithms also tolerate arbitrary and, in particular, realistic noise.  In this overview, I will place agnostic learning in the context of many traditional concepts in machine learning, such as Valiant's PAC model (1984), Fourier learning, Support Vector Machines, Decision Trees, (Inter)active Learning, and Boosting.  No prior learning knowledge will be assumed.

Sept 29

Calvin Newport

MIT

 Distributed Computing in the Age of Open Airwaves

As we enter an era of ubiquitous computing, theoreticians are faced
with a new scenario for distributed computation: large numbers of heterogeneous wireless devices competing to use the same unlicensed bands of the radio spectrum. The resulting conflicts ensure that unpredictable (sometimes even adversarial) interference is endemic throughout these bands.  Traditional radio network models -- which typically assume a single predictable communication frequency used only by devices running the same algorithm -- do not adequately capture this reality. This begs the question: can theoreticians effectively model and prove useful bounds in this chaotic setting?

In this talk, I will propose the answer is "yes." Specifically, I will describe recent research in which my collaborators and I model an unlicensed band by incarnating the diversity of different interference
behavior in an abstract adversary. This allows us to prove strong bounds that remain applicable to real world disrupted radio channels.
To support this claim I will describe our research on the canonical problem of gossip, highlighting two interesting results in particular: first, there exist connections between oblivious deterministic solutions to gossip and extremal graph theory; and second, linear-time deterministic gossip is possible even in the presence of a moderate amount of adversarial interference.

Oct 6

Laszlo Babai,

University of Chicago

Polynomial-time Theory of Matrix Groups 

The membership problem in finite groups (given by a list of generators) has attracted considerable attention over the past decades in the theory of computing as well as in computational group theory.  It was the motivation behind one of the orginal sources of the concept of interactive proofs; and most recently it was studied in connection with quantum complexity classes (Aaronson and Kuperberg, Theory of Computing 2007).

Arguably, the most important representation of finite groups is by matrices over finite fields.  I will discuss the membership problem in this model in the light of recent definitive results.

The analogous problem for permutation groups has been known since 1980 to be solvable in polynomial time.  In contrast, for matrix groups, even the one-by-one case seems to require factoring integers and discrete logarithms; so we cannot hope to avoid these obstacles in the general case.

A quarter century of increasingly intensive study by the theoretical computer science and computational group theory communities has clarified a lot of advanced questions, especially relating to the normal structure and composition factors of such a group, but only recently have these efforts added up to an answer to the basic question: at least in odd characteristic, we can now claim that group membership can be decided in randomized polynomial time, using oracles for factoring and discrete log (and therefore it is also solvable in quantum polynomial time).

Previously similar results were known for solvable matrix groups only
(Luks, FOCS 1992).

As a by-product we obtain a natural problem in BPP not known to be
in RP or coRP.

The overall procedure combines new elementary algorithms with a large body of previous work, algorithmic as well as group theoretic, much of it in the black-box-group context introduced in (B-Szemeredi, FOCS 1984) that has gained popularity in the computational group theory community over the past decade.  Some of the ingredients depend on detailed knowledge of the classification
of finite simple groups.  However, no knowledge of group theory beyond an undergraduate introduction to abstract algebra will be required for this talk.

The talk is based on joint work with Bob Beals and Akos Seress (STOC'09).

Oct 13

No Talk: MIT Monday

Oct 20

Or Meir,

Weizmann Institute

PCPs of sub-constant error via derandomized direct product

A PCP is a proof system in which the proofs can be verified by a verifier that reads only a very small part of the proof. One line of research concerning PCPs is trying to reduce their soundness error (i.e., the probability of accepting false claims) as much as possible. In particular, using low-degree curves, it is possible to construct PCP verifiers that use only two queries and have soundness error that is an inverse poly-logarithmic function in the input length.

In this talk, we show an alternative construction of such PCPs, using a simpler and less algebraic approach. This is done by extending the derandomized direct product test of Impagliazzo, Kabanets and Wigderson (STOC 09) to a construction of a PCP. To that end, we identify general properties of a PCP that allow amplifying its soundness by the means of direct product. We then show that any PCP can be transformed into one that achieves those general properties by embedding the corresponding constraint graph on a de-Bruijn graph.

No prior knowledge on PCPs will be assumed.

Joint work with Irit Dinur.

Oct 27

No TOC colloquium

in honor of

FOCS 2009

Nov 3

Ariel Procaccia,

Harvard University

f(x) marks the spot

Given a vector x of ideal locations reported by multiple selfish agents, we would like to select a location f(x) for a public facility; this abstract setting has many interpretations, such as locating a library in a city or a router on a communications network. We wish to design mechanisms for this problem that, at the same time, (i) satisfy game-theoretic desiderata, and (ii) approximately optimize a target function, e.g., the facility's sum of distances to the agents' ideal locations. I will survey recent results with respect to this problem, elaborate on their interfaces with computational social choice and algorithmic mechanism design, and position them in the context of the fresh agenda of approximate mechanism design without money. No background is required, and the presentation will endeavor to replace equations with animations.

Based on joint papers with Noga Alon, Michal Feldman, Felix Fischer, and Moshe Tennenholtz.

Nov 10

Christian Borgs,

Microsoft Research New England

 Search, Recommendations, and Spam

All modern search engines use the link structure of the web to rank web pages.  Web spammers, a.k.a. search engine optimizers, use strategically placed additional links to enhance the ranks of the web pages of their customers.  In the first part of the talk, I discuss how we can use geometric properties of the web graph to help identify spam.  My main emphasis here will be on the so-called contribution set (a set from which a given page gets most of its rank) and a local algorithm to determine this contribution set.  In the second part I will discuss recommendation systems which take into account trust relations expressed, e.g., in a social network.   In order to select from the a priori infinite number of possible recommendations algorithms based on these trust networks, we formulate several natural axioms, and discuss what these axioms imply for the design of these recommendation systems.

The talk is based on joint work with R. Andersen, J. Chayes, U. Feige, A. Flaxman, J. Hopcroft, A. Kalai, V. Mirrokni, S-H. Teng and M.Tennenholtz.

Nov 17

Rocco Servedio,

Columbia University

Average Sensitivity of Polynomial Threshold Functions

How many edges of the n-dimensional Boolean hypercube can be sliced by a degree-d polynomial surface? This question can be equivalently stated as "What is the maximum average sensitivity of any degree-d polynomial threshold function?"  In 1994 Gotsman and Linial posed this question and gave a conjectured answer:  the symmetric function slicing the middle d layers of the Boolean hypercube has the highest average sensitivity of all degree-d polynomial threshold functions.

In this work we give the first non-trivial upper bounds on average sensitivity of degree-d polynomial threshold functions (PTFs), thus making progress toward the Gotsman-Linial conjecture.  The conjecture itself remains open.

I will explain the main ideas behind our result and describe some of its applications.  These include

·          the first polynomial-time agnostic learning algorithm for degree-d polynomial threshold functions;

·         the first subexponential-time learning algorithm for AC⁰ circuits augmented with arbitrary linear threshold gates; and,

·         low-weight approximators for degree-d polynomial threshold functions.

Joint work with (various subsets of) Ilias Diakonikolas, Parikshit Gopalan, Prasad Raghavendra, Li-Yang Tan, and Andrew Wan.

Nov 24

Sanjeev Arora,

Princeton University

Computational complexity and information asymmetry in financial derivatives

CDOs and related financial derivatives have been at the center of the
current crisis and subject of ongoing regulatory overhaul.

Despite their demonstrable benefits in economic theory, derivatives
suffer from the practical drawback that pricing them accurately is often difficult even for sophisticated trading banks using powerful computers.  We propose a new explanation: the pricing problem is computationally intractable.

We also quantify the economic implications of this computational intractability. According to economic theory, derivatives are beneficial because they mitigate the effects of asymmetric information (i.e., in settings where sellers know more about the product than the buyers, a scenario studied in the classic paper of Akerloff).

We show that this may no longer hold when we take computational complexity into account. Using an Akerloff-like notion of "lemon cost" we can show that derivatives can in fact amplify the effects of asymmetric information.

Our notion of lemon cost can also differentiate between different types of derivatives, say CDOs and CDO2, supporting the traditional belief that the latter are more "complex."

Joint work with Boaz Barak, Markus Brunnermeier, and Rong Ge.

http://intractability.princeton.edu/blog/2009/10/new-paper-on-complexity-and-financial-derivatives/

Dec 1

Ran Raz,

Weizmann Institute

TBA

Dec 8

Michel Goemans,

MIT

TBA

Dec 15

Moni Naor,

Weizmann Institute

TBA