Enter your search text in the box above

Select a result to preview

my projects

Publications

Google Scholar

TCS in general

Learning theory and stats

Cryptography

Programming languages

Authors: Ferenc Bencs, Brice Huang, DL, Kuikui Liu, Guus Regts

Blurb for the non-expert:
There's this literature at the intersection of statistical physics and TCS which studies algorithmic/complexity theoretic implications of phase transitions (think ice → water → vapor). On the physics side, there's a whole landscape of heuristic calculations (some of which have been made rigorous) which suggest different ways of detecting these phase transitions (this term itself is somewhat vague/ill defined). A general template of a question here is, do these notions of phase transitions have algorithmic implications? That is, as we take a material and heat it or cool it, do certain questions around computing properties of this material become easy vs computationally intractable?

One particular category of material that physicists and computer scientists alike are especially interested in are glasses. (In fact, the canonical model of spin glasses is the Sherrington-Kirkpatrick model. S is a theoretical physicist, K is a computer scientist). On the physics side, glasses are interesting because they seem to not exhibit the kind of sharp phase transition that "most" other materials exhibit (as you heat it, glass becomes less and less viscous in a smooth manner, rather than a sharp threshold). On the CS side, it turns out that certain models of glasses called spin glasses and related techniques are relevant in the study of Bayesian optimization, network theory, neural networks, etc...

On the TCS side, one particularly interesting/active question is that of, at what temperatures is it tractable to (1) simulate the material (i.e. prepare a sample from the Gibbs distribution associated to the material) and/or (2) compute its normalizing constant aka partition function (which I've heard is very important in Bayesian type applications). These two questions turn out to be equivalent for many interesting classes of models.

Okay, so what do we do? We show how to solve question 2 for the SK model using some cool techniques from complex analysis. It turns out that one way to compute the free energy (log partition function) is by Taylor expanding around a point where it's easy to compute. This requires a suitable zero freeness result for the partition function. We show zero freeness with an application Jensen's formula (no, not Jensen's inequality, although it is the same Jensen) to the (complex) second moment of the SK model and generalizations called $p$-spin models.

Authors: Jun-Ting Hsieh, DL, Sidhanth Mohanty, Aaron Putterman, Rachel Yun Zhang

Blurb:
This is not a graph
Graph types
This is a graph
Generation of a random graph – TikZ.net

Graphs are great because they're simple to describe, and serve as a suitable model for many things like social networks, the internet, brain things, cell transcription networks, ecologies, certain games, certain physics models.

A decade or two ago, the question of graph sparsification was introduced by Benczur and Karger. As this fell into the general framework of pseudorandomness/sparsification that theoretical computer scientists love, it got picked up and inspired a line of work (which continues to this day).

In graph sparsification, you're given a graph with $n$ vertices and $m$ edges, and your goal is to output another graph, still with $n$ vertices but with $m' \ll m$ edges (much fewer edges) s.t. the new graph is still a good approximation of the original graph.

It turns out that there's a nice simple algorithm based on important sampling that gets you graphs with logarithmic average degree, or total $m' = n\log n$.

In this paper, we study the more structured question of what happens for Cayley graphs where your graph is now generated by a group. The vertices are elements of your group, and your given a set $S$ of generators, each of which specifies a set of edges ($a$ is connected to $b$ if there exists $c\in S$ s.t. $b=ca$). The goal is to subsample $S$ in a way that leads to a Cayley graph that is a good approximation of the original Cayley graph. What makes this problem harder is that edges come in packages. We can no longer sample each edge individually. Instead, each edge comes in a group of $n$ edges.

It still turns out that a more sophisticated application of importance sampling works here.

Authors: DL, Francisco Pernice, Amit Rajaraman, Ilias Zadik

Authors: Yeshwanth Cherapanamjeri, DL

Authors: Yuval Ishai, Mahimna Kelkar, DL, Yiping Ma

Abstract:
We revisit the problem of private information retrieval (PIR) in the shuffle model, where queries can be made anonymously by multiple clients.
We present the first single-server PIR protocol in this model that has sublinear per-client communication and information-theoretic security. Moreover, following one-time preprocessing on the server side, our protocol only requires sublinear per-client computation. Concretely, for every $\gamma>0$, the protocol has $O(n^{\gamma})$ communication and computation costs per (stateless) client, with $1/\poly(n)$ statistical security, assuming that a size-$n$ database is simultaneously accessed by $\poly(n)$ clients. This should be contrasted with the recent breakthrough result of Lin, Mook, and Wichs (STOC 2023) on doubly efficient PIR in the standard model, which is (inherently) limited to computational security.

Authors: Cynthia Dwork, DL, Huijia (Rachel) Lin, Pranay Tankala

Abstract:
We identify and explore connections between the recent literature on multi-group fairness for prediction algorithms and the pseudorandomness notions of leakage-resilience and graph regularity. We frame our investigation using new, statistical distance-based variants of multicalibration that are closely related to the concept of outcome indistinguishability. Adopting this perspective leads us naturally not only to our graph theoretic results, but also to new, more efficient algorithms for multicalibration in certain parameter regimes and a novel proof of a hardcore lemma for real-valued functions.

See also Rachel's talk on our paper at Simon's!

Authors: DL, Georgy Noarov, Mallesh Pai, Aaron Roth

Abstract:
We introduce a simple but general online learning framework in which a learner plays against an adversary in a vector-valued game that changes every round. Even though the learner's objective is not convex-concave (and so the minimax theorem does not apply), we give a simple algorithm that can compete with the setting in which the adversary must announce their action first, with optimally diminishing regret. We demonstrate the power of our framework by using it to (re)derive optimal bounds and efficient algorithms across a variety of domains, ranging from multicalibration to a large set of no regret algorithms, to a variant of Blackwell's approachability theorem for polytopes with fast convergence rates. As a new application, we show how to "(multi)calibeat'' an arbitrary collection of forecasters -- achieving an exponentially improved dependence on the number of models we are competing against, compared to prior work.

Authors: Richard A. Eisenberg, Guillaume Duboc, Stephanie Weirich, DL

Abstract: Despite the great success of inferring and programming with universal types, their dual—existential types—are much harder to work with. Existential types are useful in building abstract types, working with indexed types, and providing first-class support for refinement types. This paper, set in the context of Haskell, presents a bidirectional type-inference algorithm that infers where to introduce and eliminate existentials without any annotations in terms, along with an explicitly typed, type-safe core language usable as a compilation target. This approach is backward compatible. The key ingredient is to use strong existentials, which support (lazily) projecting out the encapsulated data, not weak existentials accessible only by pattern-matching.

Theses

Towards a Fundamental Theorem of Learning and Compression

Thesis for my Master's in Mathematics (2022), on finite sample compression schemes for concept classes of finite VC dimension.

Talks, Surveys, Projects

https://drive.google.com/file/d/1acK-yoakdzcgXXfZY_wOLnmeq7TICqxn/preview

Talk: Expander Graphs (Fall 2021)

Slides for a 10 minute talk on expander graphs, for the Directed Reading Program.

Talk: Hardness vs. Randomness (Spring 2021)

Slides and lecture notes for a talk I gave about Hardness vs. Randomness (Nisan, Wigderson 1994), for CIS 700 Computational Complexity.

Survey: Local Differential Privacy (Fall 2020)

Theory of differential privacy; especially in the local setting, and how it relates to classical learnability classes/results. Final project for CIS 625 Theory of Machine Learning.

Survey: A Game Theoretic Perspective on GANs and Training GANs (Spring 2021)

Generative Adversarial Networks, how they relate to game theory, and how the game theoretic perspective is being applied in research to improve generalization and trainability of GANs. Final project for NETS 412 Algorithmic Game Theory.

Project: Understanding Self-Supervised Learning through BYOL: Bootstrap-your-own-latent (Fall 2021)

Abstract: In vision, self-supervised learning is an unsupervised method of learning rich feature representations from unlabeled images that can be used for improving performance on downstream tasks. In this work, we explore bootstrap-your-own-latent (BYOL), a recently developed self-supervised learning method that reduces computational expenses and produces state-of-the-art results. We implement a simplified version of the BYOL pipeline and perform experiments to study how various settings affect performance. The results suggest that (1) self-supervised pre-training is a form of regularization to address overfitting; (2) self-supervised learning relies on access to a very large unlabeled dataset; (3) the predictor is critical to BYOL's performance; (4) augmentations must be robust enough for the network to learn meaningful image features and some are much more useful for representation learning than others; and (5) the value of the target update parameter $\tau$ is critical to BYOL's success and adding a custom schedule for updating $\tau$ during training can boost performance.

An implementation of a parser, type checker, and evaluator. Support for user defined Algebraic Data Types, pattern matching, mutual recursion, higher rank polymorphism, impredicativity. Evaluator based on a small step operational semantics. Type checker is inspired by the Quick Look paper. Final project for CIS 552 Advanced Programming.

A library with definitions and fundamental results for one-categories in Cubical Agda, a constructive/computational implementation of Homotopy Type Theory.