Algorithms
Understanding Black-box Predictions via Influence Functions
How can we explain the predictions of a black-box model? In this paper, we use influence functions — a classic technique from robust statistics — to trace a model’s prediction through the learning algorithm and back to…
Dynamic Program Analysis-based Approach for Algorithm Recognition and Program Repair
In this talk, I will describe techniques for recognizing the high-level algorithmic idea of a program and its applications in feedback generation for introductory programming education. Both techniques are based on dynamic program analysis, in…
Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time
Sampling integers with Gaussian distribution is a fundamental problem that arises in almost every application of lattice cryptography, and it can be both time consuming and challenging to implement. Most previous work has focused on…
Provable Algorithms for ML/AI Problems
Machine learning (ML) has demonstrated success in various domains such as web search, ads, computer vision, natural language processing (NLP), and more. These success stories have led to a big focus on democratizing ML and…
Mixed-integer quadratic programming is in NP
Uniformization of distributional limits of graphs
Benjamini and Schramm (2001) showed that distributional limits of finite planar graphs with uniformly bounded degrees are almost surely recurrent. The major tool in their proof is a lemma which asserts that for a limit…
Accelerating Stochastic Gradient Descent
There is widespread sentiment that it is not possible to effectively utilize fast gradient methods (e.g. Nesterov’s acceleration, conjugate gradient, heavy ball) for the purposes of stochastic optimization due to their instability and error accumulation,…
Homomorphic Encryption for Arithmetic of Approximate Numbers
We suggest a method to construct a homomorphic encryption scheme for approximate arithmetic. It supports approximate addition and multiplication of encrypted messages, together with the rescaling procedure for managing the magnitude of plaintext. This procedure…
