I will discuss techniques, structural results, and open problems from two of my recent papers, in the context of a broader area of work on the motivating question: "how do we get the most from our data?"

In the first part of the talk, I will...

Computer Science and Discrete Mathematics (CSDM)

I will discuss techniques, structural results, and open problems from two of my recent papers, in the context of a broader area of work on the motivating question: "how do we get the most from our data?"

In the first part of the talk, I will...

What combinatorial properties are likely to be satisfied by a random subspace over a finite field? For example, is it likely that not too many points lie in any Hamming ball of fixed radius? What about any combinatorial rectangle of fixed side...

Let X and Y be normed spaces. In functional analysis, a ``theorem on factorization through L2'' refers to the following type of statement:

Every bounded linear operator A mapping X to Y (i.e. sup_x ||A(x)||_Y/||x||_X

Such factorization...

What can we say on a convex body from seeing its projections? In the 80s, Lutwak introduced a collection of measurements that capture this question. He called them the affine quermassintegrals. They are affine invariant analogues of the classical...

Let X and Y be normed spaces. In functional analysis, a ``theorem on factorization through L2'' refers to the following type of statement:

Every bounded linear operator A mapping X to Y (i.e. sup_x ||A(x)||_Y/||x||_X

Such...

Indistinguishability obfuscation, introduced by [Barak et. al. Crypto’2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new...

Suppose we have a cancellative binary associative operation * on a finite set X. We say that it is delta-associative if the proportion of triples x, y, z such that x*(y*z) = (x*y)*z is at least delta.

Gowers and Long studied somewhat...

We prove new lower bounds on the well known Gap-Hamming problem in communication complexity. Our main technical result is an anti-concentration bound for the inner product of two independent random vectors. We show that if A, B are arbitrary subsets...

Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets in a (possibly higher...

Nima Anari

We introduce two new notions for polynomials associated with discrete set-valued probability distributions. These notions generalize well-studied properties like real-stability and log-concavity, but unlike them robustly degrade under a number of...