Computer Science and Discrete Mathematics (CSDM)

A weighted graph H is a sparsifier of a graph G if H has much fewer edges than G and, in an appropriate technical sense, H "approximates" G. Sparsifiers are useful as compressed representations of graphs and to speed up certain graph algorithms. In...

This talk aims to summarize a project I was involved in during the past 5 years, with the hope of explaining our most complete understanding so far, as well as challenges and open problems. The main messages of this project are summarized below; I...

The dichotomy between structure and randomness plays an important role in areas such as combinatorics and number theory. I will discuss a similar dichotomy in complexity theory, and illustrate it with three examples of my own work: (i) An...

There are significant gaps between legal and technical thinking around data privacy. Technical standards such as k-anonymity and differential privacy are described using mathematical language whereas legal standards are not rigorous from a...

In the talk, I will explain the algorithm (and its analysis) for testing whether a number is a prime, invented by Agrawal, Kayal, and Saxena.

I'll be presenting some joint work with Ian Mertz scheduled to appear at STOC 2020. The study of the Tree Evaluation Problem (TEP), introduced by S. Cook et al. (TOCT 2012), is a promising approach to separating L from P. Given a label in [k] at...

In this talk I will describe the notion of "agreement tests" that are motivated by PCPs but stand alone as a combinatorial property-testing question. I will show that high dimensional expanders support agreement tests, thereby derandomizing direct...

A theorist's dream is to show that hard instances/obstructions for an (optimal) algorithm can be used as gadgets to prove tight hardness reductions (which proves optimality of the algorithm). An example of such a result is that of Prasad Raghavendra...

In this talk I will describe the notion of "agreement tests" that are motivated by PCPs but stand alone as a combinatorial property-testing question. I will show that high dimensional expanders support agreement tests, thereby derandomizing direct...

Consider the p-biased distribution over 0,1n, in which each coordinate independently is sampled according to a p-biased bit. A sharp-threshold result studies the behavior of Boolean functions over the hypercube under different p-biased measures, and...