New York Area Theory Day
Organized by: IBM/NYU/Columbia
Friday, April 25, 2014
Davis Auditorium, Columbia University, New York
External sponsorship by: Google
The New York Area Theory Day is a semiannual 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 45) hourlong
presentations by leading theoretical computer scientists about
stateoftheart 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
09:30  10:00: Coffee and bagels
10:00  10:55: Dr. Vahab Mirrokni (Google Research)
Ad Allocation: Online Problems and Mechanism Design
10:55  11:05: Short break
11:05  12:00: Dr. Jennifer Chayes (Microsoft Research)
The Power of Locality for Network Algorithms
12:00  02:00: Lunch break (lunch NOT provided)
02:00  02:55: Prof. Venkatesan Guruswami (CMU)
Polar codes: Reliable communication with complexity scaling polynomially in the gap to Shannon capacity
02:55  03:15: Coffee break
03:15  04:10: Prof. Adam Smith (Penn State)
Private Analysis of Graphs
For directions, please see here.
To subscribe to our mailing list, follow instructions at
http://www.cs.nyu.edu/mailman/listinfo/theoryny
Organizers:
Yevgeniy Dodis: dodis@cs.nyu.edu
Tal Rabin: talr@us.ibm.com
Cliff Stein: cliff@ieor.columbia.edu
==================================================================
Abstracts
Ad Allocation: Online Problems and Mechanism Design
Dr. Vahab Mirrokni
Google Research
Handling advertiser budget and capacity constraints is a central issue
in online advertising, resulting in many interesting optimization and
game theoretic problems. In this talk, we discuss two aspects of
dealing with budget constraints: the online stochastic optimization
problem and ad allocation/pricing mechanisms with strategic
advertisers.
In the first part, we survey recent results focusing on simultaneous
adversarial ad stochastic approximations, improved approximations for
stochastic variants of the problem, and finally the multiobjective
online optimization. In this regard, we also pose several remaining
open problems.
In the second part, we discuss the mechanism design problems in the
online setting, present the framework of clinching auctions to deal
with these constraints, and conclude with open problems in this area.
==================================================================
The Power of Locality for Network Algorithms
Dr. Jennifer Chayes
Microsoft Research
Given the massive size of many networks, conventional algorithms which
scale as polynomials in the network size are woefully inadequate. In
the first part of this talk, we consider how to use locality to
deliver much more efficient algorithms (quasilinear or even
sublinear in the network size) for quantities and questions like
pagerank, coverage, diffusion, and determining the most influential
nodes. In this second part of this talk, we consider another aspect
of locality, namely the question of local data access. Many large
networks are encoded locally, e.g., with adjacency lists. How does
the nature of the data access impact the efficiency of algorithms?
Surprisingly, we show that small differences in data access can lead
to very large differences in efficiency and approximability of network
algorithms. As an example, we consider a covering problem which
arises naturally for recruiters on social networks, and show how small
differences between the information on neighbors in LinkedIn and
Facebook lead to large differences in their utility to recruiters.
==================================================================
Polar codes: Reliable communication with complexity scaling polynomially
in the gap to Shannon capacity
Prof. Venkatesan Guruswami
CMU
Shannon's monumental 1948 work laid the foundations for the rich
fields of information and coding theory. The quest for *efficient*
coding schemes to approach Shannon capacity has occupied researchers
ever since, with spectacular progress enabling the widespread use of
errorcorrecting codes in practice. Yet the theoretical problem of
approaching capacity arbitrarily closely with polynomial complexity
remained open except in the special case of erasure channels.
In 2008, Arikan proposed an insightful new method for constructing
capacityachieving codes based on channel polarization. In this talk,
I will begin by surveying Arikan's celebrated construction of polar
codes, and then discuss our proof (with Patrick Xia) that, for all
binaryinput symmetric memoryless channels, polar codes enable
reliable communication at rates within epsilon > 0 of the Shannon
capacity with block length (delay), construction complexity, and
decoding complexity all bounded by a *polynomial* in the gap to
capacity, i.e., by poly(1/epsilon). Polar coding gives the *first
explicit construction* with rigorous proofs of all these properties;
previous constructions were not known to achieve capacity with less
than exp(1/epsilon) decoding complexity.
We establish the capacityachieving property of polar codes via a
direct analysis of the underlying martingale of conditional entropies,
without relying on the martingale convergence theorem. This yields
effective bounds on the speed of polarization, implying that polar
codes can operate at rates within epsilon of capacity at a block
length bounded by poly(1/epsilon). The generator matrix of such polar
codes can also be constructed in deterministic polynomial time by
algorithmically computing an adequate approximation of the
polarization process.
==================================================================
Private Analysis of Graphs
Prof. Adam Smith
Penn State
We discuss algorithms for the private analysis of network data. Such
algorithms work on data sets that contain sensitive relationship
information (for example, romantic ties). Their goal is to compute
approximations to global statistics of the graph while protecting
information specific to individuals. Our algorithms satisfy a rigorous
notion of privacy, called node differential privacy. Intuitively, it
means that an algorithm's output distribution does not change
significantly when a node and all its adjacent edges are removed from
a graph, or when a new node with an arbitrary set of edges is added to
the graph.
A key component of our work is the design of efficiently computable
Lipschitz extensions of commonly studied graph statistics. Given a
graph statistic f, we seek to design a new function g that is
efficiently computable and "robust" to the addition or removal of
vertices, yet agrees with f on as large a set of graphs as possible.
Our techniques are based on combinatorial analysis, network flow, and
linear and convex programming.
Based on joint work with Shiva Kasiviswanathan, Kobbi Nissim and Sofya
Raskhodnikova (from TCC 2013 as well as recent, ongoing work).
==================================================================
