Title: Computing on Encrypted Data; Extremely Fast and Simple Abstract:  Consider the following setting for computing on private data. A client uploads an encryption of a big input X to an untrusted server, and then wishes to make an unbounded number of queries f(X) while hiding f and X from the server and using only its secret […]

Title: Robustly Guarding Polygons Abstract: A fundamental set cover problem that arises in geometric domains is the classic Art Gallery Problem: given a geometric domain (e.g., a polygon), place a set of points within the domain, such that every point in it is seen by at least one of the guards. This problem has many variants […]

Title: From Learning Theory to Cryptography: Provable Guarantees for AI Abstract: Ensuring that AI systems behave as intended is a central challenge in contemporary AI. This talk offers an exposition of provable mathematical guarantees for learning and security in AI systems. Starting with a classic learning-theoretic perspective on generalization guarantees, we present two results quantifying […]

Title: High Dimensional Expanders: Structure and Applications Abstract: Expanders are graphs that are both edge-sparse and well connected. They have been an instrumental tool in many results in mathematics and computer science, some of which seem to have little connection to graphs at all. High dimensional expanders (HDXs) are hypergraph analogues of expander graphs — sparse […]

Title: A Global View of Locality Through the Lens of Distributed Computing, Parallel Computing, and Learning Theory Abstract: Locality, i.e. computing under partial knowledge, is a fundamental challenge that can manifest itself in many versatile ways: from a distributed network where each processor has to rely on local information to solve global tasks (such as […]

Abstract: The field of artificial intelligence (AI) is undergoing a paradigm shift, moving from neural networks trained for narrowly defined tasks (e.g., image classification and machine translation) to general-purpose models such as ChatGPT. These models are trained at unprecedented scales to perform a wide range of tasks, from providing travel recommendations to solving Olympiad-level math […]