Colloquium Details
New York Area Theory Day
Speaker: IBM/NYU/Columbia
Location: Havemeyer Hall, Columbia University 309
Date: April 25, 2014, 9:30 a.m.
Host: Columbia University, New York
Synopsis:
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.
Program
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 http://www.columbia.edu/about_columbia/map/havemeyer.html
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 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 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).
Notes:
In-person attendance only available to those with active NYU ID cards.