New York Area Theory Day

Organized by: IBM/NYU/Columbia
Friday, May 4, 2012
Davis Auditorium, 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. Michael Kearns (U Penn)
                     Experiments in Social Computation

10:55 - 11:05      Short break

11:05 - 12:00      Prof. Eli Ben-Sasson (Technion and Microsoft Research - New England)
                    An additive combinatorics approach relating rank to communication complexity 

12:00 - 02:00      Lunch break

02:00 - 02:55      Dr. Aleksander Madry   (Microsoft Research New England)
                     Online Algorithms and the K-server Conjecture

02:55 - 03:15      Coffee break

03:15 - 04:10      Dr. Shubhangi Saraf (IAS)
                     The Method of Multiplicities



For directions, please see here


To subscribe to our mailing list, follow instructions at
 http://www.cs.nyu.edu/mailman/listinfo/theory-ny

Organizers:

Yevgeniy Dodis   dodis@cs.nyu.edu
Tal Rabin        talr@us.ibm.com
Baruch Schieber  sbar@us.ibm.com
Rocco Servedio   rocco@cs.columbia.edu


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

Abstracts

		Experiments in Social Computation

			 Michael Kearns
		   (University of Pennsylvania)

What does the theory of computation have to say about the emerging 
phenomena of crowdsourcing and social computing? Most successful
applications of crowdsourcing to date have been on problems we might
consider "embarrassingly parallelizable" from a computational perspective.
But the power of the social computation approach is already evident,
and the road cleared for applying it to more challenging problems.

In part towards this goal, for a number of years we have been conducting
controlled human-subject experiments in distributed social computation
in networks with only limited and local communication. These experiments
cast a number of traditional computational problems --- including graph
coloring, consensus, independent set, market equilibria, and voting
--- as games of strategic interaction in which subjects have financial
incentives to collectively "compute" global solutions. I will overview
and summarize the many behavioral findings from this line of
experimentation, and draw broad comparisons to some of the predictions
made by the theory of computation and microeconomics.



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


       	   An additive combinatorics approach relating rank to 
			communication complexity 

			  Eli Ben-Sasson
	    (Technion and Microsoft Research - New England)

For a {0,1}-valued matrix M let CC(M) denote the deterministic 
communication complexity of the boolean function associated with M.
It is well-known since the work of Mehlhorn and Schmidt [STOC 1982]
that CC(M) is bounded from above by rank(M) and from below by log rank(M) 
where rank(M) denotes the rank of M over the field of real numbers. 
Determining where in this range lies the true worst-case value of CC(M)
is a fundamental open problem in communication complexity. The state of
the art is

	      log^{1.631} rank(M) < CC(M) < 0.415 rank(M),

the lower bound is by Kushilevitz [unpublished, 1995] and the upper bound
 is due to Kotlov [Journal of Graph Theory, 1996]. Lovasz and Saks [FOCS 1988]
conjecture that CC(M) is closer to the lower bound, i.e., CC(M) < log^c(rank(M))
for some absolute constant c --- this is the famous ''log-rank conjecture''
--- but so far there has been no evidence to support it, even giving a slightly
non-trivial (o(rank(M))) upper bound on the communication complexity.

Our main result is that, assuming the Polynomial Freiman-Ruzsa (PFR) conjecture
in additive combinatorics, there exists a universal constant c such that

		     CC(M)< c rank(M)/ log rank(M).

Although our bound is stated using the rank of M over the reals, our proof goes
by studying the problem over the finite field of size 2, and there we bring to
bear a number of new tools from additive combinatorics which we hope will
facilitate further progress on this perplexing question.

In more detail, our proof is based on the study of the ''approximate duality
conjecture'' which was suggested by Ben-Sasson and Zewi [STOC 2011] and studied
there in connection to the PFR conjecture. First we improve the bounds on
approximate duality assuming the PFR conjecture. Then we use the approximate
duality conjecture (with improved bounds) to get our upper bound on the
communication complexity of low-rank martices.

Joint work with Shachar Lovett (IAS) and Noga Ron-Zewi (Technion) 


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

	  Online Algorithms and the K-server Conjecture

			Aleksander Madry
		(Microsoft Research New England)

Traditionally, in the problems considered in optimization, one
produces the solution only after the whole input is made available.
However, in many real-world scenarios the input is revealed gradually,
and one needs to make irrevocable decisions along the way while having
only partial information on the whole input. This motivates us to
develop models that allow us to address such scenarios.

In this talk, I will consider one of the most popular approaches to
dealing with uncertainty in optimization: the online model and
competitive analysis; and focus on a central problem in this area: the
k-server problem. This problem captures many online scenarios - in
particular, the widely studied caching problem - and is considered by
many to be the "holy grail" problem of the field.

I will present a new randomized algorithm for the k-server problem
that is the first online algorithm for this problem that achieves
polylogarithmic competitiveness.

Based on joint work with Nikhil Bansal, Niv Buchbinder, and Joseph
(Seffi) Naor.


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

		    The Method of Multiplicities

			   Shubhangi Saraf
			        (IAS)

Polynomials have played a fundamental role in the construction of objects with
interesting combinatorial properties, such as error correcting codes,
pseudorandom generators, randomness extractors etc. Somewhat strikingly,
polynomials have also been found to be a powerful tool in the analysis of
combinatorial parameters of objects that have some algebraic structure. This
method of analysis has found applications in works on list-decoding of error
correcting codes, constructions of randomness extractors, and in obtaining
strong bounds for the size of Kakeya Sets. Remarkably, all these applications
have relied on very simple and elementary properties of polynomials
such as the sparsity of the zero sets of low degree polynomials.

In this talk we will discuss improvements on several of the results mentioned
above by a more powerful application of polynomials that takes into account
 the information contained in the *derivatives* of the polynomials. We call
this technique the ``method of multiplicities". The information about higher
multiplicity vanishings of polynomials, which is encoded in the derivative
polynomials, enables us to meaningfully reason about the zero sets of
polynomials of degree much higher than the underlying field size.

We will discuss some of these applications of the method of multiplicities, to
obtain improved constructions of error correcting codes, and qualitatively
tighter analyses of Kakeya sets, and randomness extractors.

(Based on joint works with Zeev Dvir, Swastik Kopparty, Madhu Sudan, Sergey
Yekhanin)


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