[Busec] Fwd: REMINDER: IBM-NYU-Columbia Theory Day, May 4th, 2012 (@ Columbia)

Ran Canetti canetti at tau.ac.il
Thu Apr 26 17:53:24 EDT 2012

-------- Original Message --------
Subject: 	REMINDER: IBM-NYU-Columbia Theory Day, May 4th, 2012 (@ Columbia)
Date: 	Thu, 26 Apr 2012 17:21:18 -0400
From: 	Tal Rabin <talr at us.ibm.com>
To: 	undisclosed-recipients:;

Please distribute the following announcement at your institutions,
and hope to see you on Friday, May 4th, 2012 at Columbia!

Sorry for duplicates.
-- Tal, Rocco, Yevgeniy and Baruch


                   The IBM Research|NYU|Columbia Theory Day
                           Friday, May 4th, 2012

The Theory Day will be held at the Davis auditorium,
412 Schapiro (CEPSR) building, Columbia University, New York.


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, MSR NE)
                    An Additive Combinatorics Approach to the Log-rank

12:00  -  2:00    Lunch break

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

   2:55  -  3:15    Coffee break

   3:15  -  4:10    Dr. Shubhangi Saraf (IAS)
                    The Method of Multiplicities

For directions, please see

To subscribe to our mailing list, follow instructions at

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



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 to the Log-rank Conjecture

Eli Ben-Sasson

For a {0,1}-valued matrix M let CC(M) denote the deterministic
communication complexity of the boolean function associated with M. The
log-rank conjecture of Lovasz and Saks [FOCS 1988]
states that CC(M)<= log^c(rank(M)) for some absolute constant c where
rank(M) denotes the rank of M over the field of real numbers.

We show that CC(M)<= c rank(M)/ log rank(M) for some absolute constant
c, assuming a well-known conjecture from additive combinatorics, known
as the Polynomial Freiman-Ruzsa (PFR) conjecture.

Our proof is based on the study of the "approximate duality conjecture"
which was recently 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 the
aforementioned upper bound on the communication complexity of low-rank
matrices, and this part uses the methodology suggested by Nisan and
Wigderson [Combinatorica 1995].

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)


The Method of Multiplicities

Shubhangi Saraf

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
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

More information about the Busec mailing list