Title: The lens of Abelian embeddings.

Abstract:

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 discuss this notion and some problems it arises from various areas in TCS, such as hardness of approximation, multi-player parallel and property testing. 

Depending on time, we will discuss a few partial results on the study on this notion as well as some of their applications.

Mostly based on joint works with Amey Bhangale, Subhash Khot