MSR/MIT Theory Reading Group

I will overview results on learning structured single-dimensional distributions, spending most of my time with two simple families:
- Poisson Binomial distributions: these are sums of independent but not necessarily iid Bernoullis; and

We introduce the notion of a fully *key*-homomorphic encryption
scheme, construct such a scheme based on the learning with errors
assumption, and show a number of applications, including:

* attribute-based and functional encryption schemes with
super-compact keys;

Incidence geometry is a part of combinatorics studying the possible intersection patterns of lines, circles, or other simple shapes. For example, given L lines in the plane, what is the maximum possible number of points that lie in at least r lines?

In this talk we will focus on constructing multi-prover interactive proofs (MIPs) that are sound
against *no-signaling* (cheating) strategies, for any deterministic computation.
Such MIPs were studied in the context of MIPs with provers that share quantum entanglement,