Colloquium Details
New York Area Theory Day, December 2016
Speaker: IBM/NYU/Columbia
Location: Warren Weaver Hall 109
Date: December 2, 2016, 9:15 a.m.
Host: Courant Institute of Mathematical Sciences, New York University
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.
For directions, please see here.
To subscribe to our mailing list, follow the instructions here.
Organizers:
Program
| 9:15 - 9:45 | Coffee and bagels |
| 9:45 - 10:40 | Professor Sofya Raskhodnikova Differentially Private Analysis of Graphs |
| 10:40 - 10:55 | Coffee break |
| 10:55 - 12:00 | Short presentations by students and postdocs Rafael Oliveira, Shikha Singh, Ryan Rogers, Robert Hildebrand, Steven Wu, Clément Canonne, Stuart Hadfield |
| 12:00 - 2:00 | Lunch break |
| 2:00 - 2:55 | Professor Aleksander Madry Continuous Optimization: The “Right” Language for Graph Algorithms? |
| 2:55 - 3:05 | Coffee break |
| 3:05 - 3:45 | Short presentations by students and postdocs Sasha Golovnev, Jonathan Gryak, Neil Lutz, Jalaj Upadhyay, Amey Bhangale |
| 3:45 - 3:55 | Coffee break |
| 3:55 - 4:50 | Professor Uriel Feige Approximate Modularity Revisited |
| 5:00 - 7:00 | Follow-up social White Oak Tavern, 21 Waverly Pl |
Speakers
Professor Sofya Raskhodnikova (Penn State University)
Differentially Private Analysis of Graphs
Many types of data can be represented as graphs, where nodes correspond to individuals and edges capture relationships between them. Examples include datasets capturing “friendships” in an online social network, financial transactions, email communication, doctor-patient relationships, and romantic ties. On one hand, such datasets contain sensitive information about individuals. On the other hand, global information that can be gleaned from their analysis can provide significant benefits to society. In this talk, we will discuss algorithms for analyzing network data that satisfy a rigorous notion of privacy, called node differential privacy, and present new tools for designing such algorithms.
Based on joint work with Adam Smith (FOCS 2016).
Professor Aleksander Madry (MIT)
Continuous Optimization: The “Right” Language for Graph Algorithms?
Traditionally, we view graphs as purely combinatorial objects and tend to design our graph algorithms to be combinatorial as well. In fact, in the context of algorithms, “combinatorial” became a synonym of “fast”.
Recent work, however, shows that a number of such “inherently combinatorial” graph problems can be solved much faster using methods that are very “non-combinatorial”. Specifically, by approaching these problems with tools and notions borrowed from linear algebra and, more broadly, from continuous optimization. A notable examples here are the recent lines of work on the maximum flow problem, the bipartite matching problem, and the shortest path problem in graphs with negative-length arcs.
This raises an intriguing question: Is continuous optimization a more suitable and principled optics for fast graph algorithms than the classic combinatorial view?
In this talk, I will discuss this question as well as the developments that motivated it.
Professor Uriel Feige (Weizmann Institute and Princeton)
Approximate Modularity Revisited
Set functions with convenient properties (such as submodularity) appear in application areas of current interest, such as algorithmic game theory, and allow for improved optimization algorithms. It is natural to ask (e.g., in the context of data driven optimization) how robust such properties are, and whether small deviations from them can be tolerated. We consider two such questions in the important special case of linear set functions.
One question is whether any set function that approximately satisfies the modularity equation (linear functions satisfy the modularity equation exactly) is close to a linear function. The answer to this is positive as shown by Kalton and Roberts [1983] (and further improved by Bondarenko, Prymak, and Radchenko [2013]). We revisit their proof idea that is based on expander graphs, and provide significantly stronger upper bounds by combining it with new techniques. Furthermore, we provide improved lower bounds for this problem.
Another question is how to learn a linear function $h$ that is close to an approximately linear function $f$, while querying the value of $f$ on only a small number of sets. We present a deterministic algorithm that makes only linearly many (in the number of items) nonadaptive queries, by this improving over a previous algorithm of Chierichetti, Das, Dasgupta and Kumar [2015] that is randomized and makes more than a quadratic number of queries. Our learning algorithm is based on a Hadamard transform.
Joint work with Michal Feldman and Inbal Talgam-Cohen
Short Presentations by Students and Postdocs
Rafael Oliveira (Princeton University)
Operator Scaling and Applications to TCS, Math and Beyond
I will describe the problem of operator scaling, which is a generalization of matrix scaling, and its myriad applications to TCS, Math and Physics. I will also discuss our contributions to the solution of the operator scaling problem, and the next frontiers to be explored.
Shikha Singh (Stony Brook University)
The Power of Rational Proofs
Interactive proofs model a world where a verifier delegates computation to an untrustworthy prover, verifying the prover's claims before accepting them. In this talk we will discuss the power of "rational proofs", that are an interactive proof model in which the prover is rational rather than untrustworthy---he may lie, but only to increase his payment (received from the verifier).
Ryan Rogers (University of Pennsylvania)
Leveraging Privacy in Data Analysis and Mechanism Design
My research focuses on applying differentially privacy to problems in economics, statistical hypothesis testing, and adaptive data analysis in machine learning. The results from my research can be split roughly into two main areas: 1) incorporating privacy as an additional constraint into an otherwise classical problem; 2) using privacy as a tool to solve new problems where privacy may not be a primary concern.
Robert Hildebrand (IBM T.J. Watson Research Center)
Integer Polynomial Optimization in Fixed Dimension
Complexity of linear integer programming is well understood in fixed dimension. For the same question with instead a polynomial objective function, we will discuss recent results on algorithms, complexity, and applications of this problem.
Steven Wu (University of Pennsylvania)
Privacy, Learning and Game Theory
My research focuses on differential privacy, learning theory and algorithmic economics, and the fundamental connections among these areas. In this talk, I will highlight a powerful algorithmic technique that is useful for solving the problems in these areas.
Clément Canonne (Columbia University)
Many Eggs, More Baskets: New Insights from New Models
The fields of property testing and sublinear algorithms form, by now, an established and very active research area. This is about them (also, eggs).
Stuart Hadfield (Columbia University)
Quantum Algorithms for Approximate Optimization
The recently proposed Quantum Approximate Optimization Algorithm [Farhi et al. 2016] gives an approach to approximating combinatorial optimization problems on a quantum computer. We derive novel constructions for a variety of constraint satisfaction problems. Joint work with Eleanor G. Rieffel (NASA QuAIL).
Sasha Golovnev (New York University)
Dispersers and Circuit Lower Bounds
In this talk, we will see that many classical circuit lower bounds can be stated as lower bounds for dispersers. We will also explore several new connections between strong dispersers and lower bounds in different circuit models.
Jonathan Gryak (CUNY Graduate Center)
Non-Commutative Cryptography Using Polycyclic and Metabelian Groups
In contrast to common key exchanges, non-commutative cryptography seeks to utilize algebraic structures with non-commutative operations to create secure cryptographic systems. In this talk, I will discuss cryptographic systems that employ polycyclic and metabelian groups, along with their attendant hardness assumptions.
Neil Lutz (Rutgers University)
Fractal Geometry via Algorithmic Information
I will describe algorithmic fractal dimensions, which measure the information density of individual points, and how these dimensions give insight into classical fractal geometry.
Jalaj Upadhyay (Penn State University)
Differential Privacy in the Streaming and Local Model
In this talk, we state two results: (i) limits of differentially private low rank approximation when the matrix is continually updated, and (ii) how much interaction is required for private learning in the local model.
Amey Bhangale (Rutgers University)
Cube vs Cube Low degree Test
We revisit the Raz-Safra plane-vs.-plane test and study the closely related cube vs. cube test. We provide an alternate way of proving a low degree test which is arguably much simpler than the previously known proofs in the low error regime.