New York Area Theory Day

Organized by: IBM/NYU/Columbia
Friday, May 13, 2011
412 Schapiro (CEPSR) building, Columbia University, New York.

The New York Area 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 presentations by leading theoretical computer scientists about state-of-the-art 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:

Program

 9:30  - 10:00   Coffee and bagels

10:00  - 10:55   Prof. Sanjeev Arora (Princeton University)
		 Probabilistically Checkable Proofs: the First Two Decades

10:55  - 11:05   Short break

11:05  - 12:00   Prof. Silvio Micali (MIT)
		 The Second-Knowledge Mechanism

12:00  -  2:00   Lunch break

 2:00  -  2:55   Dr. Lisa Zhang (Bell Labs)
		 Energy Aware Network Design 

 2:55  -  3:15   Coffee break

 3:15  -  4:10   Prof. Mario Szegedy (Rutgers University)
		 Tardos and Moser meet Lovasz 


For directions, please see here


If you would like to be added to the mailing list, please send
email to talr@us.ibm.com.

Organizers:

Yevgeniy Dodis   dodis@cs.nyu.edu
Tal Malkin       tal@cs.columbia.edu
Tal Rabin        talr@us.ibm.com
Baruch Schieber  sbar@us.ibm.com 

==================================================================

Abstracts

      Probabilistically Checkable Proofs: the First Two Decades

		       Prof. Sanjeev Arora
		      (Princeton University)

The area of probabilistically checkable proofs (PCPs) is two decades old
this year. At its heart is a counterintuitive phenomenon: mathematical
proofs can be checked by looking at as few as three bits in them! This
realization transformed our understanding of computational complexity
theory, especially the approximability of NP-hard problems. Along the
way it has also thrown up many surprises, improving our understanding of
several existing areas such as cryptography, approximation algorithms,
average case complexity, subexponential algorithms, constraint
satisfaction problems, embeddings of metric spaces, convex programming
relaxations of combinatorial problems, learning theory, etc. It has
spawned new areas of study such as property testing, list decoding, and
the unique games conjecture. This survey talk will be a broad sweep
through these connections, trying to explain why this area holds so much
interest in theoretical computer science, with pauses at some of my
favorite open problems and promising directions. It should be
accessible to a broad audience.


==================================================================


		The Second-Knowledge Mechanism

		      Prof. Silvio Micali
			     (MIT)

In mechanism design, the classical way to model the players.
uncertainty about their opponents in a setting of incomplete
information is assuming a "Bayesian."  We instead model it in a
SET-THEORETIC, and yet LEVERAGEABLE, way.

In auctions of a single good, we put forward a new revenue benchmark
B, lying between the highest and second-highest valuation, and
(1)     provide a new mechanism that perfectly and robustly achieves B
under mutual knowledge of rationality, and
(2)     prove that no mechanism can even approximate B in a robust way,
not only in dominant/undominated strategies, but also ``at
equilibrium".

Joint work with Jing Chen.


==================================================================

		  Energy Aware Network Design

			 Dr. Lisa Zhang
			  (Bell Labs)

Given a network, a set of demands and a cost function f, the min-cost
network design problem is to route all demands with the objective of
minimizing the total cost f(l_e) over all links e, where l_e is the
traffic load on e under the routing. We focus on cost functions of the
form f(x) = sigma + x^alpha with f(0)=0. For alpha <= 1, the problem
corresponds to the well-studied Buy-at-Bulk network design.

We examine the less studied scenario of alpha>1, which is motivated by
power minimization in network design. This cost function aims to model a
range of computing and communication devices for which doubling
processing speed more than doubles the power consumption. We present a
polylogarithmic approximation algorithm. Our approach builds upon
techniques such as well-linked decomposition, construction of expanders
via matchings, and edge-disjoint routing in well-connected graphs.

We will also briefly touch upon a scheduling problem in the context of
power minimization.

This is joint work with Matthew Andrews and Spyros Antonakopoulos.


==================================================================

		 Tardos and Moser meet Lovasz

		     Prof. Mario Szegedy
		     (Rutgers University)

Lovasz's Local Lemma (LLL) finds a wide variety of applications in
combinatorics and computer science.
It allows to deduce the existence of a global solution for any system of
constraints, whose variable set has intersection graph G,
as long as the probability that any given constraint is not satisfied
is below a threshold that depends only on the maximal degree of G.
Beck has turned Lovasz's existence proof into an algorithm, but with a
weaker dependence on the max degree. Following several improvements
Moser, and Moser and Tardos have developed a very simple
algorithm, which is also optimal, when the degree tends to infinity.
Their analysis reaches a natural bound (in terms of the entire G) with
which the lemma was stated in the original paper of Lovasz.

Lovasz's original lemma is more general, and the events are not
necessarily defined via an intersection graph for a family of
constraints, but rather by a graph G that describes dependencies.
For a fixed dependency graph G, the exact criterion under which the
general LLL applies, is given by Shearer. We show that the analysis of
the MT algorithm can be improved all the way to Shearer's bound. In
particular, whenever the probabilities are 1-epsilon factor within
Shearer's bound, the Moser-Tardos algorithm runs in expected time at
most n /epsilon. This makes the efficient version an exact match to the
non-efficient one.
We also give a deeper reason for this co-incidence: A variant of the
Moser-Tardos argument can actually prove the general
LLL (although not "efficiently," but "efficiency" does not make much
sense here, anyway).

Finally, we show that variable framework represents a real restriction.
The LLL bound for the variable version for some G is higher
than for the general version. This, of course, raises the question if
the MT algorithm can efficiently achieve this higher bound.

Joint work with Kashyap Kolipaka

==================================================================