Computer Science Colloquium
New York Area Theory Day
IBM/NYU/Columbia,
May 10, 2013
9:30AM
Warren Weaver Hall, 109
251 Mercer Street
New York, NY 10012
(Directions)
Spring 2013 Colloquia Calendar
Host
Courant Institute of Mathematical Sciences
External sponsorship by: Google
Synopsis
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 meeting is free and open to everyone;
in particular, students are encouraged to attend.
9:3010:00: Coffee and bagels
10:0010:55: Prof. Tim Roughgarden (Stanford University)
Extension Theorems for the Price of Anarchy
10:5511:05: Short break
11:0512:00: Dr. Allison Lewko (Microsoft Research New England)
On the Complexity of Asynchronous Agreement Against Powerful Adversaries
12:0002:00: Lunch break (lunch not provided)
02:0002:55: Prof. Avi Wigderson (Institute for Advanced Study)
Grey Boxes, Population Recovery and Partial Identification
02:5503:15: Coffee break
03:1504:10: Dr. Ankur Moitra (Institute for Advanced Study)
An Information Complexity Approach to Extended Formulations
For directions, please see
http://www.cims.nyu.edu/direct.html and
http://cs.nyu.edu/csweb/Location/directions.html (building 46)
To subscribe to our mailing list, follow instructions at
http://www.cs.nyu.edu/mailman/listinfo/theoryny
Organizers:
Xi Chen: xichen@cs.columbia.edu
Yevgeniy Dodis: dodis@cs.nyu.edu
Tal Rabin: talr@us.ibm.com
========
Abstracts
========
Extension Theorems for the Price of Anarchy
Prof. Tim Roughgarden (Stanford University)
Abstract: The price of anarchy is a measure of the inefficiency of
selfish behavior that has been successfully analyzed in many
applications, including network routing, resource allocation, network
formation, and even models of basketball. It is defined as the
worstcase ratio between the welfare of a Nash equilibrium and
that of an optimal solution.
Purestrategy Nash equilibria  where each player deterministically
picks a single action  are often easier to analyze than their more
general cousins like mixedstrategy Nash equilibria (where players can
randomize) and BayesNash equilibria (where players are uncertain
about what game they're playing in). For this reason, the price of
anarchy is often analyzed, at least initially, only for a game's
purestrategy Nash equilibria. But as much as he or she might want
to, the conscientious researcher cannot stop there  such equilibria
might not exist, might be hard to compute, and are relevant only when
all players' preferences are common knowledge. Can we obtain price of
anarchy bounds for more general equilibrium concepts without working
any harder than we already do to analyze purestrategy Nash equilibria?
Ideal would be an "extension theorem" that could be used in the
following ``blackbox'' way: (1) prove a bound on the price of anarchy
of purestrategy Nash equilibria of a game; (2) invoke the extension
theorem to conclude immediately that the exact same approximation
bound applies to some more general equilibrium concept. Such an
extension theorem would dodge the obvious deterrents from
generalizing price of anarchy bounds beyond pure Nash equilibria 
no extra work, and no loss in the approximation guarantee. In this
talk, I'll describe two such extension theorems: one for the possible
outcomes generated by the repeated play of noregret learners, and
one for games of incomplete information.
=============================
On the Complexity of Asynchronous Agreement Against Powerful Adversaries
Dr. Allison Lewko (Microsoft Research New England)
Abstract: In this talk, we will present new techniques for proving lower
bounds on the running time of randomized algorithms for distributed
consensus in the presence of mobile failures. We begin with the
observation that the early randomized algorithms for consensus
presented by Bracha and BenOr succeed against even stronger
adversaries than they were initially designed to resist. We then prove
that the exponential expected running time of these algorithms is an
inherent consequence of that stronger resilience. This furthers our
understanding of the kind of failures that can (or cannot) be corrected
by polynomial time randomized algorithms. This is joint work with
Mark Lewko.
=============================
Grey Boxes, Population Recovery and Partial Identification
Prof. Avi Wigderson (Institute for Advanced Study)
Abstract: The talk, like the title, will have three parts.
In the first, I will describe a new learning model we call "restriction
access". This model aims at generalizing prevailing "blackbox"
access to functions when trying to learn the "device" (e.g. circuit,
decision tree, polynomial ...) which computes them. We propose a
"greybox" access that allows certain partial views of the device,
obtained from random restrictions. The PAClearning analog of our
model is able to efficiently learn decision trees and DNFs, which are
currently beyond reach in the standard "blackbox" version of
PAClearning.
To analyze some of these learning algorithms, we study several
natural "population recovery" problems in which an unknown distribution
over an unknown population of vectors needs to be recovered from
partial or noisy samples. Such problems naturally arise in many other
contexts in learning, clustering, statistics, data mining and database
privacy, where loss and error may be introduced by nature, inaccurate
measurements, or on purpose. We give fairly efficient algorithms to
recover the data under fairly general assumptions, when loss and
noise are close to the information theoretic limit (namely, nearly
completely obliterate the original data).
The third part introduces a new combinatorial structure we call a
partial identification (PID) graph, which underlies our algorithms.
While standard IDs are subsets of features (vector coordinates) that
uniquely identify an individual in a population, partial IDs allow
ambiguity (and "imposters"), and thus can be shorter. PID graphs
capture this imposterstructure. PID graphs yield strategies for
dimension reductions of recovery problems, and the reassembly of
this local pieces of statistical information to a global one. The
combinatorial heart of this work is proving that every set of vectors
admits partial IDs with "cheap" PID graphs (and hence efficient
recovery). We further show how to find such nearoptimal PIDs
efficiently.
Based on joint works with Zeev Dvir, Anup Rao and Amir Yehudayoff
=============================
An Information Complexity Approach to Extended Formulations
Dr. Ankur Moitra (Institute for Advanced Study)
Often it is possible to express a given polytope $P$ as the projection
of a higher dimensional polytope $Q$ and in so doing to drastically
reduce the number of facets needed. We call $Q$ an extended
formulation for $P$. In fact, small extended formulations are known
for a number of polytopes that arise in combinatorial optimization and
yet there are many polytopes that we do not expect to have a small
extended formulation  e.g. polytopes that capture the solutions to
hard optimization problems. Can we prove unconditional results that
these polytopes do not have small extended formulations?
Recently, there has been a revival of interest in this question. A
breakthrough result of Fiorini et al (STOC 2012) established that the
TSP polytope has no subexponential sized extended formulation.
Subsequently Braun et al (FOCS 2012) proved that the clique polytope
has no subexponential $O(n^{1/2  \epsilon})$approximate extended
formulation either. Here we give a new approach to these lower bounds
based on information complexity  roughly a toogoodtobetrue
extended formulation would allow us to sample from a distribution
using too few bits of entropy, and this is the means by which we prove
our lower bounds. We use this framework to prove that the clique
polytope has no subexponential $O(n^{1  \epsilon})$approximate
extended formulation, thus giving an optimal and unconditional lower
bound that matches Hastad's celebrated hardness of approximation
results for clique.
This is based on joint work with Mark Braverman.
