Computer Science and Discrete Mathematics (CSDM)

In randomized experiments, such as a medical trials, we randomly assign the treatment, such as a drug or a placebo, that each experimental subject receives. Randomization can help us accurately estimate the difference in treatment effects with high...

Proof Complexity studies the length of proofs of propositional tautologies in various restricted proof systems. One of the most well-studied is the Cutting Planes proof system, which captures reasoning which can be expressed using linear...

We propose a new hierarchy of semidefinite programming relaxations for inference problems. As test cases, we consider the problem of community detection in block models. The vertices are partitioned into k communities, and a graph is sampled...

We investigate the approximability of the following optimization problem, whose input is an n-by-n matrix A and an origin symmetric convex set C that is given by a membership oracle: "Maximize the quadratic form as x ranges over C." This is a rich...

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...