# Computer Science and Discrete Mathematics (CSDM) ### Getting the most from our data

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... ### Thresholds for Random Subspaces, aka, LDPC Codes Achieve List-Decoding Capacity

Mary Wootters

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... ### Factorization through L2, Rounding and Duality Part 2

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... ### New isoperimetric inequalities for convex bodies

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... ### Factorization through L2, Rounding and Duality

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 from Well-Founded Assumptions

Huijia (Rachel) Lin

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... ### Associativity testing

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

### Anti-concentration and the Gap-Hamming problem

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... ### On the extension complexity of random polytopes

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... ### Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More

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