Theory Day - Friday, November 14, 2003

The Theory Day will be held at Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, Auditorium 109, New York.

Program

9:30 - 10:00	Coffee and Bagels
10:00 - 10:55	Prof. Oded Goldreich (Weizmann Institute of Science and Radcliffe Institute for Advanced Studies at Harvard University) On the Implementation of Huge Random Objects
10:55 - 11:05	Short Break
11:05 - 12:00	Dr. Chandra Chekuri (Bell Labs) Maximum Coverage Problem with Group Budget Constraints and Applications
12:00 - 2:00	Lunch Break
2:00 - 2:55	Dr. Dana Ron (Radcliffe Institute for Advanced Study at Harvard and Tel-Aviv University) Testing Bipartiteness: The Dense, The Sparse, and The General
2:55 - 3:15	Coffee Break
3:15 - 4:10	Prof. Russell Impagliazzo (UCSD and IAS) Hardness as Randomness: a Survey of Universal Derandomization

For directions, please see http://www.cims.nyu.edu/direct.html and http://cs.nyu.edu/web/Location/directions.html (building 46)

To subscribe to our mailing list, follow instructions at http://www.cs.nyu.edu/mailman/listinfo/theory-ny

Hosts:

Yevgeniy Dodis dodis@cs.nyu.edu, (212) 998-3084
Tal Malkin tal@cs.columbia.edu
Tal Rabin talr@watson.ibm.com
Baruch Schieber sbar@watson.ibm.com

Colloquium Information: http://cs.nyu.edu/web/Calendar/colloquium/index.html

Itinerary

On the Implementation of Huge Random Objects

Prof. Oded Goldreich
Weizmann Institute of Science and Radcliffe Institute for Advanced Studies at Harvard University

We initiate a general study of pseudo-random implementations of huge random objects, and apply it to a few areas in which random objects occur naturally. For example, a random object being considered may be a random connected graph, a random bounded-degree graph, or a random error-correcting code with good distance. A pseudo-random implementation of such type T objects must generate objects of type T that can not be distinguished from random ones, rather than objects that can not be distinguished from type T objects (although they are not type T at all).

We will model a type T object as a function, and access objects by queries into these functions. We investigate supporting both standard queries that only evaluates the primary function at locations of the user's choice (e.g., edge queries in a graph), and complex queries that may ask for the result of a computation on the primary function, where this computation is infeasible to perform with a polynomial number of standard queries (e.g., providing the next vertex along a Hamiltonian path in the graph). Joint work with Shafi Goldwasser and Asaf Nussboim.

Maximum Coverage Problem with Group Budget Constraints and Applications

Dr. Chandra Chekuri
Bell Labs

We consider the following problem. We are given m sets from a universe, each of which is colored by one of \ell distinct colors. We are to pick k (<= \ell) sets of distinct colors so as to maximize the size of their union. If m=\ell the problem is the same as the maximum coverage problem and the greedy algorithm is an "optimal" (1-1/e)-approximation algorithm. For the general problem we show that a greedy algorithm is a 1/2-approximation algorithm. We then demonstrate several non-trivial applications of this simple covering abstraction and discuss some extensions. Joint work with Amit Kumar.

Testing Bipartiteness: The Dense, The Sparse, and The General

Dr. Dana Ron
Radcliffe Institute for Advanced Study at Harvard and Tel-Aviv University

Property Testing is the study of the following family of problems: given query access to an object (e.g., a graph or a function), a testing algorithm must decide whether the object has a predetermined property (e.g., 3-colorability or linearity) or whether it is "epsilon-far" from having the property. In "\epsilon-far" we mean that an epsilon fraction of the object should be modified so that it obtains the property.

Property testing algorithms exist for many types of objects and properties. This talk will focus on testing graph properties, and in particular on a basic graph property that has received quite a bit of attention: Bipartiteness. It turns out that for this property, as well as others, the complexity of testing varies significantly with the model used for testing, where different models are appropriate for different types of graphs.

This talk will survey three results (and mention a few other related results).

1. The first result is an algorithm for testing bipartiteness of graphs that are dense. The complexity of this algorithm is independent of the size of the graph.
2. The second result is an algorithm of testing bipartiteness of graphs that have bounded degree. The complexity of this algorithm grows (roughly) like sqrt{n} where n is the number of graph vertices, and there is a matching lower bound.
3. The third, and most recent, result studies a model that is appropriate for all types of graphs. This work bridges the gap between the first two results: as long as the average degree of the graph is at most sqrt{n}, it obtains the same complexity as the second algorithm, and as the average degree increases, it approaches the complexity of the first algorithm. Here too the bound is almost tight.

Hardness as Randomness: a Survey of Universal Derandomization

Prof. Russell Impagliazzo
UCSD and IAS

We survey recent developments in the study of probabilistic complexity classes. While the evidence seems to support the conjecture that probabilism can be deterministically simulated with relatively low overhead, i.e., that P=BPP, it also indicates that this may be a difficult question to resolve. In fact, proving that probalistic algorithms have non-trivial deterministic simulations is basically equivalent to proving circuit lower bounds, either in the algebraic or Boolean models.

In this talk, I'll survey some results from the theory of derandomization. I'll stress connections to other questions, especially circuit complexity, explicit etractors, hardness amplification, and error-correcting codes. Much of the talk is based on work by Valentine Kabanets, Avi Wigderson and myself, but I'll also include results by many other researchers.