Computer Science/Discrete Mathematics Seminar II

A predicate $P:\Sigma^k \to {0,1}$ is said to be linearly embeddable if the set of assignments satisfying it can be embedded in an Abelian group. 

In this talk, we will present this notion and mention problems it relates to from various areas. These areas include hardness of approximation, multi-player parallel repetition, property testing and additive combinatorics. Depending on time, we will discuss a few partial results on the study of this notion, as well as applications.

Mostly based on joint works with Amey Bhangale, Subhash Khot.