Computer Science Colloquium

New York Area Theory Day


April 25, 2014 9:30AM
Havemeyer Hall, 309
Columbia University
New York, NY

Spring 2014 Colloquia Calendar


Columbia University, New York
External sponsorship by: Google


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 meeting is free and open to everyone;
in particular, students are encouraged to attend.


9: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 - 2:00 Lunch break (lunch NOT provided)

2:00 - 2:55 Prof. Venkatesan Guruswami (CMU)
Polar codes: Reliable communication with
complexity scaling polynomially in the gap to Shannon capacity

2:55 - 3:15 Coffee break

3:15 - 4:10 Prof. Adam Smith (Penn State)
Private Analysis of Graphs

For directions, please see

If you would like to be added to the mailing list, please send
email to

Yevgeniy Dodis
Tal Rabin
Cliff Stein


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

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 multi-objective
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 (quasi-linear or even
sub-linear 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
error-correcting 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
capacity-achieving 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
binary-input 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 capacity-achieving 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).

top | contact webmaster