New York Area Theory Day
Organized by: IBM/NYU/Columbia
Friday, April 17, 2015
Davis Auditorium, Davis auditorium, 412 Schapiro (CEPSR) building, 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 Craig Gentry (IBM Research)
Encrypted Computation in a Quantum World
10:55  11:05: Short break
11:05  12:00 Jenn Wortman Vaughan (Microsoft Research)
Combinatorial Prediction Markets via Convex
Cost Functions: An Overview of Recent Research
12:00  02:00: Lunch break (lunch NOT provided)
2:00  2:55 Moses Charikar (Princeton)
The Hidden Objective of Spectral Clustering?
02:55  03:15: Coffee break
3:15  4:10 Subhash Khot (NYU)
On Monotonicity Testing and Boolean
Isoperimetric Type Theorems
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 Malkin tal@cs.columbia.edu
Tal Rabin talr@us.ibm.com
==================================================================
Abstracts
Encrypted computation in a quantum world
Craig Gentry, IBM Research
Can we use a quantum computer to efficiently factor a homomorphicallyencrypted
integer (using a homomorphic verson of Shor's algorithm)? This talk
considersthe question of how to extend FHE to the quantum domain, referencing
work mainly by other people, like Broadbent and Jeffery:
http://mysite.science.uottawa.ca/abroadbe/publications.html.
==================================================================
Combinatorial Prediction Markets via Convex Cost Functions:
An Overview of Recent Research
Jenn Wortman Vaughan, Microsoft Research
A prediction market is a financial market designed to aggregate
information. In a typical prediction market, participants trade
securities with payoffs linked to the outcome of a future event, such
as a security that will be worth $1 if a Democrat wins the 2016 US
Presidential election and $0 otherwise. An expectation maximizing
trader who believes that the probability of a Democrat winning is p
should be willing to purchase this security at any price below $p,
or sell it at any price above $p, and the current market price can
be viewed as the traders' collective estimate of how likely it is
that a Democrat will win the election.
To facilitate trades, prediction markets can be operated by an automated
market maker, a centralized algorithmic agent that is always willing to
buy and sell securities at some current market price. However, when
the number of outcomes is very large, it is generally infeasible to run
a simple prediction market over the full outcome space. I will begin by
describing a general framework for the design of securities markets over
combinatorial or infinite state or outcome spaces. Our framework enables
the design of computationally efficient markets tailored to an
arbitrary, yet relatively small, space of securities. We prove that any
market satisfying a set of intuitive conditions must price securities
via a convex cost function which can be constructed via conjugate duality.
Rather than deal with an exponentially large or infinite outcome space
directly, our framework only requires solving an optimization problem.
The techniques employed have deep mathematical connections to techniques
used in online learning, exponential families, and variational inference.
Time permitting, I will go on to discuss several recent extensions of
this framework including a class of market makers that can profit from
disagreement among traders, a principled approach for the market maker
to modify liquidity in specific segments of a combinatorial market when partial
information about the outcome is revealed, and a way of incorporating limit
orders into continuous time markets.
==================================================================
The Hidden Objective of Spectral Clustering?
Moses Charikar
Princeton University
We introduce and study a new notion of graph partitioning, intimately connected
to kmeans clustering. Informally, our graph partitioning objective asks for the
optimal spectral simplification of a graph as a disjoint union of k normalized
cliques. It is a variant of graph decomposition into expanders. Optimizing this
new objective is equivalent to clustering the effective resistance embedding of
the graph. Our approximation algorithm for the new objective is closely related
to spectral clustering: it optimizes the kmeans objective on a certain smoothed
version of the resistive embedding. In order to illustrate the power of our new
notion, we show that approximation algorithms for our new objective can be used
in a black box fashion to approximately recover a partition of a graph into k
pieces given a guarantee that a good partition exists.
Joint work with Pranjal Awasthi, Ravishankar Krishnaswamy, and Ali Kemal Sinop.
==================================================================
On Monotonicity Testing and Boolean Isoperimetric Type Theorems
Subhash Khot, NYU
We show a directed and robust analogue of a boolean isoperimetric type
theorem of Talagrand. As an application, we give a monotonicity testing
algorithm that makes O(sqrt{n}/epsilon^2) nonadaptive queries to a
function f:{0,1}^n > {0,1}, always accepts a monotone function and
rejects a function that is epsilonfar from being monotone with
constant probability.
Joint work with Dor Minzer and Muli Safra.
The paper is available at http://eccc.hpiweb.de/report/2015/011/
==================================================================
