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

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/theory-ny

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

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