The IBM Research  NYU  Columbia THEORY DAY
Friday, November 14, 2003
New York University, Courant Institute Room 109 Warren Weaver Hall 251 Mercer Street New York, NY 10012
The IBM Research  NYU  Columbia Theory Day is a semiannual
conference,
aimed to bring together people in the New York Metropolitan area for
one day of
interaction and discussion. The Theory Day features several
(usually 45) hourlong
presentations by leading theoretical computer scientists about
stateoftheart advances
in various areas. Some presentations give a survey of the latest
advances in some area,
while others may concentrate on a particular result.
The meeting is free and open to everyone; in particular, students are
encouraged to attend.
Program:
9:30  10:00 Coffee and bagels
10:00  10:55 Prof. Oded Goldreich On the Implementation of Huge Random Objects
10:55  11:05 Short break
11:05  12:00 Dr. Chandra Chekuri Maximum Coverage Problem with Group Budge Constraints and Applications 12:00  2:00 Lunch break
2:00  2:55 Dr. Dana Ron Testing Bipartiteness: The Dense, The Sparse, and The General
2:55  3:15 Coffee break
3:15  4:10 Prof. Russell Impagliazzo Hardness as Randomness: a Survey of Universal Derandomization
The Theory Day will be held at Room 109 Warren Weaver Hall, Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012 Click here or here for directions.
To subscribe to our mailing list, follow instructions here.
Organizers:
Yevgeniy Dodis (NYU)
Tal Malkin (Columbia)
Tal Rabin (IBM Research)
Baruch Schieber (IBM
Research)
Abstracts:
On 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 pseudorandom 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 boundeddegree graph, or a random errorcorrecting code with good distance. A pseudorandom 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" (11/e)approximation algorithm. For the general problem we show that a greedy algorithm is a 1/2approximation algorithm. We then demonstrate several nontrivial 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 TelAviv 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., 3colorability or linearity) or whether it is "epsilonfar" from having the property. In "\epsilonfar" 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. 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 nontrivial 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 errorcorrecting 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.
"Every day is
Theory Day"
