Colloquium Details

New York Area Theory Day

Speaker: IBM/NYU/Columbia

Location: Schapiro (CEPSR) Building, Columbia University 412

Date: April 17, 2015, 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 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 - 2:00 Lunch break (lunch not provided)

2:00 - 2:55 Moses Charikar (Princeton) The Hidden Objective of Spectral Clustering?

2:55 - 3:15 Coffee break

3:15 - 4:10 Subhash Khot (NYU) On Monotonicity Testing and Boolean Isoperimetric Type Theorems

For directions, please see http://www.cs.columbia.edu/theory/directions.html

If you would like to be added to the mailing list, please send email to xc2198@columbia.edu.

Organizers: Yevgeniy Dodis dodis@cs.nyu.edu Tal Malkin tal@cs.columbia.edu Tal Rabin talr@us.ibm.com

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

Abstracts

Craig Gentry, IBM Research

Title: Encrypted computation in a quantum world

Abstract: Can we use a quantum computer to efficiently factor a homomorphically-encrypted integer (using a homomorphic verson of Shor's algorithm)? This talk considers the 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.