Theory Day  Friday, November 14, 2003
New York University
Room 109 Warren Weaver Hall
251 Mercer Street
New York, NY 100121185
The Theory Day will be held at Courant Institute of Mathematical Sciences,
New York University, 251 Mercer Street, Auditorium 109, New York.
Program
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/theoryny
Hosts:
Yevgeniy Dodis dodis@cs.nyu.edu, (212) 9983084
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 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).
 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 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.
top  contact webmaster@cs.nyu.edu
