Abstracts for the talks are given below. See the main page for schedule and location information.

Ilias Diakonikolas

Columbia University

In recent years we initiated a systematic investigation to develop the theory of multiobjective approximation along similar rigorous lines as the approximation of single objective problems. We address the problem of computing efficiently a succinct approximation of the Pareto curve using as few solutions as possible. If we are to select only a certain number of solutions, how shall we pick them so that they represent as accurately as possible the whole spectrum of possibilities?

Time permitting, we will discuss a different notion of approximation and present some of the many open problems in this area.

(Based on joint works with Mihalis Yannakakis.)

Venkatesan Guruswami

Univ. of Washington and Institute for Advanced Study

We give a new construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Our expanders have a short and self-contained description and analysis, based on the algebraic ideas underlying the recent list-decodable error-correcting codes of Parvaresh and Vardy (FOCS `05).

Our expanders can be interpreted as "randomness condensers" that achieve near-optimal compression of a weak random source while preserving all of its entropy. We also show, using ideas from the work of Guruswami and Rudra (STOC'06), that a natural construction based on Reed-Solomon codes yields a condenser that retains a (1 - delta) fraction of the source min-entropy, for any desired constant delta > 0.

Our results reduce the task of extracting randomness from sources of arbitrary min-entropy rate to extracting randomness from sources of min-entropy rate arbitrarily close to 1, which is a much easier task. Using this connection, we obtain a new construction of randomness extractors that extract 99.9% of the source entropy using a logarithmic (up to constant factors) length seed. Our construction is much simpler than the previous construction of Lu et al. (STOC `03) that achieved a similar result, and in addition improves upon it when the error parameter is small (e.g. 1/poly(n)).

Joint work with Christopher Umans and Salil Vadhan.

Yahoo Research

The k-means method is a widely used clustering technique that seeks to minimize the average squared distance between points in the same cluster. Although it offers no accuracy guarantees, its simplicity and speed are very appealing in practice. By augmenting k-means with a very simple, randomized seeding technique, we obtain an algorithm that is \Theta(log k)-competitive with the optimal clustering. Our experiments show that this augmentation improves both the speed and the accuracy of k-means, often quite dramatically.

Spyros Antonakopoulos (Columbia University)

Emanuele Viola (Columbia University)

A pseudorandom generator is an efficient deterministic algorithm that stretches a randomly chosen seed into a sequence which is much longer but nevertheless "fools" certain randomness tests, in the sense that the tests cannot distinguish it from random. In this talk we focus on the randomness tests that correspond to low-degree polynomials in n variables over a finite field, say GF(2).

For the special case of degree-1 polynomials, Naor and Naor ('90) give a generator with optimal seed length s=O(log n). This generator has been one of the most celebrated results in pseudorandomness, with applications ranging from derandomization to PCP's. On the other hand, the case of higher degree has seen little progress, with only a couple of papers (Luby, Velickovic, and Wigderson, '93; Bogdanov, '05) giving much worse seed length s > 2^(sqrt(log n)). In particular, prior to our work generators with logarithmic seed length were not known even for polynomials of degree 2.

In this work we present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the so-called Gowers norms. Using this approach, we obtain the following main results:

Our generator for degree-d polynomials is simply the component-wise sum of d generators for degree-1 polynomials (on independent seeds).

Joint work with Andrej Bogdanov.

Jason Hartline

Northwestern University

As the Internet has developed to become the single most important arena for resource sharing among parties with diverse and selfish interests, traditional algorithmic and distributed systems approaches are insufficient. To prevent undesirable Internet phenomena such as spam in email systems, bid-sniping in eBay's auction marketplace, free-loading in file-sharing networks, and click-fraud in Internet advertising; game-theoretic and economic considerations must be made. This issue is addressed by the economics field of mechanism design. Consider a mechanism to be a protocol in which selfish agents interact with a central server that then chooses an outcome (e.g., which agents are given access to which Internet resources) and possible payments (sometimes it is necessary to make agents pay for the resources they use).

The first half of this talk surveys the seminal 1981 work of economist Roger Myerson who was recognized last Thursday with the 2007 Nobel Prize in Economics. His work gave a characterization of the kinds of outcomes that are implementable by a mechanism. From this characterization, he reduces the problem of optimizing the total payments (i.e., the profit of the mechanism) to the problem optimizing the social welfare (i.e., total utility generated by the outcome selected). This result has since directly and indirectly implied countless other significant results in economics, hence the Nobel recognition.

For the second part of this talk we discuss implications and extensions of this result to the design of Internet algorithms. In particular, implementation of good mechanisms often requires the agents make payments. E.g., spam wound not exist in an email mechanism that charged one cent for each email sent. Yet, many Internet protocols do not allow payment to be made. Would you pay for email? A computational approach to solve this problem is to use computational payments instead of monetary payments. E.g., to send an email the sender's computer must first solve a computational task that provably takes ten seconds to solve; this would effectively stop email spam. Notice that in order to obtain a desirable outcome (no spam) we have to waste the computational resources of good agents (which is a loss to society). We show how Myerson's characterization can be used to design a mechanism that optimizes the social welfare when payments are not monetary but in instead in units of wasted resources. These results apply in very general settings.

Elliot Anshelevich

Rensselaer Polytechnic Institute

We define a problem called Simplex Matching, and show that it is solvable in polynomial time. While Simplex Matching is interesting in its own right as a nontrivial extension of non-bipartite min-cost matching, its main value lies in many (seemingly very different) problems that can be solved using our algorithm. For example, suppose that we are given a graph with terminal nodes, non-terminal nodes, and edge costs. Then, the Terminal Backup problem, which consists of finding the cheapest forest connecting every terminal to at least one other terminal, is reducible to Simplex Matching. Simplex Matching is also useful for various tasks that involve forming groups of at least 2 members, such as project assignment and variants of facility location.

In an instance of Simplex Matching, we are given a hypergraph H with edge costs, and edge size at most 3. We show how to find the min-cost perfect matching of H efficiently, if the edge costs obey a simple and realistic inequality that we call the Simplex Condition. The algorithm we provide is relatively simple to understand and implement, but difficult to prove correct. In the process of this proof we show some powerful new results about covering cubic graphs with simple combinatorial objects.

Anup Rao

Institute for Advanced Studies

It is a widely acknowledged that the physical universe is unpredictable. In computer science this unpredictability, modelled as randomness, turns out to be an enabling feature in algorithm design, cryptography and distributed computing.

Unfortunately, there is a gap between the physical assumption of unpredicatibility and the computer science model of pure randomness. Physical sources don't yield pure independent random bits, instead they produce "impure" bits, with some entropy.

The area of extraction of randomness attempts to convert unpredictability into pure randomness either by injecting few pure random bits (which is good enough for algorithmic usage), or by combining multiple sources of pure randomness (which may be the only way to produce cryptographically strong randomness).

In this talk we describe work along the second direction above: We show how to deterministically extract high quality randomness from a source which was generated by a small width branching program or a small space algorithm. This seems like a model that could capture defective sources of randomness in nature and extractors for such sources could be useful in the construction of pseudorandom generators for space bounded machines.

Tal Rabin

IBM TJ Watson Research Center

We investigate the question of whether security of protocols in the information-theoretic setting (where the adversary is computationally unbounded) implies the security of these protocols under concurrent composition. This question is motivated by the folklore that all known protocols that are secure in the information-theoretic setting are indeed secure under concurrent composition. We provide answers to this question for a number of different settings (i.e., considering perfect versus statistical security, and concurrent composition with adaptive versus fixed inputs). Our results enhance the understanding of what is necessary for obtaining security under composition, as well as providing tools (i.e., composition theorems) that can be used for proving the security of protocols under composition while considering only the standard stand-alone definitions of security.

Joint work with Eyal Kushilevitz and Yehuda Lindell

Costas Daskalakis

UC Berkeley

Based on joint work with Christos Papadimitriou

Vinod Vaikuntanathan

Massachusetts Institute of Technology

Integer *lattices* have emerged to be a powerful alternative to number-theory as a source of hard problems for cryptography. Cryptographic schemes based on lattices are attractive for several reasons: their computations are simple and of low complexity, they have thus far resisted quantum attacks, and their security can be based on the *worst-case* hardness of lattice problems. Unfortunately, the use of lattices in cryptography so far has been limited to relatively simple primitives such as collision-resistant hashing and public-key encryption.

In this talk, we will describe a new way to securely generate and exploit natural "trapdoors" in lattices. The cryptographic applications include various kinds of trapdoor functions, simple and efficient digital signature schemes, oblivious transfer, and identity-based encryption, all based on *worst-case* lattice assumptions.

The talk will be self-contained.

Joint work with Craig Gentry and Chris Peikert.

Back to Fall 2007 Theory Seminar main page