## The IBM Research | NYU | Columbia THEORY DAY Friday, November 14, 2003

New York University, Courant Institute Room 109 Warren Weaver Hall251 Mercer Street New York, NY 10012

The IBM Research | NYU | Columbia Theory Day is a semi-annual 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 4-5) hour-long
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 bagels10:00  - 10:55   Prof. Oded Goldreich		 On the Implementation of Huge Random Objects10: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 10012Click 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 pseudo-random implementations of hugerandom objects, and apply it to a few areas in which random objectsoccur naturally.  For example, a random object being considered may bea random connected graph, a random bounded-degree graph, or a randomerror-correcting code with good distance.  A pseudo-randomimplementation of such type T objects must generate objects of typeT that can not be distinguished from random ones, rather than objectsthat can not be distinguished from type T objects (although they arenot type T at all).We will model a type T object as a function, and access objects byqueries into these functions. We investigate supporting both standardqueries that only evaluates the primary function at locations of theuser's choice (e.g., edge queries in a graph), and complex queries thatmay ask for the result of a computation on the primary function, wherethis computation is infeasible to perform with a polynomial number ofstandard queries (e.g., providing the next vertex along a Hamiltonianpath 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 auniverse, each of which is colored by one of \ell distinct colors. Weare to pick k (<= \ell) sets of distinct colors so as to maximize thesize of their union.  If m=\ell the problem is the same as the maximumcoverage problem and the greedy algorithm is an "optimal"(1-1/e)-approximation algorithm.  For the general problem we show thata greedy algorithm is a 1/2-approximation algorithm. We thendemonstrate several non-trivial applications of this simple coveringabstraction 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 testingalgorithm 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 epsilonfraction of the object should be modified so that it obtains the property.                                                                                Property testing algorithms exist for many types of objects andproperties.  This talk will focus on testing graph properties, and inparticular on a basic graph property that has received quite a bit ofattention: Bipartiteness.  It turns out that for this property, as wellas others, the complexity of testing varies significantly with the modelused for testing, where different models are appropriate for differenttypes of graphs.                                                                                This talk will survey three results (and mention a few other relatedresults).(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 complexityclasses.  While the evidence seems to support the conjecture thatprobabilism can be deterministically simulated with relatively lowoverhead, i.e., that P=BPP, it also indicates that this may be adifficult question to resolve.  In fact, proving that probalisticalgorithms have non-trivial deterministic simulations is basicallyequivalent to proving circuit lower bounds, either in the algebraic orBoolean 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 Wigdersonand myself, but I'll also include results by many other researchers.

"Every day is Theory Day"