Colloquium Details
IBM Research NYU/Columbia Theory Day
Speaker:
Location: Warren Weaver Hall 109
Date: November 14, 2003, 9:30 a.m.
Host: Yevgeniy Dodis
Synopsis:
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).
- 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.
- 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.
- 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.
This talk is based on joint works with Oded Goldreich, Shafi Goldwasser, Tali Kaufman, and Michael Krivelevich.
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.
Notes:
In-person attendance only available to those with active NYU ID cards.