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

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 homomorphically-encrypted
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 k-means 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 k-means 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) non-adaptive queries to a
function f:{0,1}^n --> {0,1}, always accepts a monotone function and
rejects a function that is epsilon-far from being monotone with
constant probability.

Joint work with Dor Minzer and Muli Safra.

The paper is available at http://eccc.hpi-web.de/report/2015/011/

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