|
New York Area Theory Day - Spring 2017
Friday, April 28, 2017
Organized by: IBM/NYU/Columbia
External Sponsorship by: Google
Davis Auditorium, 412 Schapiro (CEPSR) Building,
Columbia University, New York (Directions)
Program:
9:30 - 10:00 Coffee and bagels
10:00 - 10:55 Professor Ran Canetti
On Single-Server Private Information Retrieval with Sublinear Work for Server
10:55 - 11:05 Short break
11:05 - 12:00 Professor Alina Ene
From Minimum Cut to Submodular Minimization: Leveraging the Decomposable Structure
12:00 - 2:00 Lunch break
2:00 - 2:55 Dr. Zeyuan Allen-Zhu
Faster Stochastic Gradient Descent: From Nesterov's Momentum to Katyusha Momentum
2:55 - 3:15 Coffee break
3:15 - 4:10 Professor Oded Regev
A Reverse Minkowski Theorem
4:30 - 5:30 Follow-up social (location: Bier International)
For directions, please see here.
To subscribe to our mailing list, follow instructions here.
Organizers:
Alex Andoni
Yevgeniy Dodis
Krzysztof Onak
======================================================================
Prof. Ran Canetti (Boston University and Tel Aviv University)
On Single-Server Private Information Retrieval with Sublinear Work for Server
Private Information Retrieval (PIR) allows clients to obtain data from public
databases without disclosing the locations accessed. Traditionally, the stress
is on preserving sublinear work for the client, while the server's work is taken
to inevitably be at least linear in the database size. Can we have schemes where
the server's amortized per query work is sublinear? While we know how to do it
when the database is split among multiple non-colluding servers, the existence
of single-server PIR with sublinear amortized server work has remained open.
We present a number of single-server PIR schemes where, following a
polynomial-work preprocessing stage, the per-query work of both server and
client is poly-logarithmic in the database size. The schemes offer different
security properties under a range of assumptions. All schemes are based on
low-degree extensions of the database in high-dimensional finite fields, akin to
Reed-Muller encoding, along with additional mechanisms that allow for local
decoding that hides the decoded points.
Joint work with Justin Holmgren and Silas Richelson.
==================================================================
Prof. Alina Ene (Boston University)
From Minimum Cut to Submodular Minimization: Leveraging the Decomposable
Structure
Submodular function minimization is a fundamental optimization problem that
arises in several applications in machine learning and computer vision. The
problem is known to be solvable in polynomial time, but general purpose
algorithms have high running times and are unsuitable for large-scale problems.
Recent work aims to obtain very practical algorithms for minimizing functions
that are sums of “simple” functions. This class of functions provides an
important bridge between functions with a rich combinatorial structure --
notably, the cut function of a graph -- and general submodular functions, and it
brings along powerful combinatorial structure reminiscent of graphs as well as a
fair bit of modeling power that greatly expands its applications. In this talk,
we describe recent progress on designing very efficient algorithms for
minimizing decomposable functions and understanding their combinatorial
structure.
This talk is based on joint work with Huy Nguyen (Northeastern University) and
Laszlo Vegh (London School of Economics).
==================================================================
Dr. Zeyuan Allen-Zhu (Institute for Advanced Study and Princeton)
Faster Stochastic Gradient Descent: From Nesterov's Momentum to Katyusha
Momentum
Nesterov's momentum is famously known for being able to accelerate
“full-gradient descent”, and thus useful in building fast first-order
algorithms. However, in the offline stochastic setting, counterexamples exist
and prevent Nesterov's momentum from providing similar acceleration, even if the
underlying problem is convex. In this talk, I shall discuss a Katyusha momentum
framework that provides the first direct acceleration to stochastic gradient
descent. This work is going to appear in STOC 2017.
==================================================================
Prof. Oded Regev (New York University)
A Reverse Minkowski Theorem
Informally, Minkowski's first theorem states that lattices that are globally
dense (have small determinant) are also locally dense (have lots of points in a
small ball around the origin). This fundamental result dates back to 1891 and
has a very wide range of applications.
I will present a proof of a reverse form of Minkowski's theorem, conjectured by
Daniel Dadush in 2012, showing that locally dense lattices are also globally
dense (in the appropriate sense).
Based on joint papers with Daniel Dadush and Noah Stephens-Davidowitz.
==================================================================
|
