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. This talk will revolve around the notion of Abelian embeddings and different contexts it appears in. In particular, we will discuss:
-
Approximation algorithms and hardness of approximation for constraint satisfaction problems.
Multi-player parallel repetition theorems.
Additive combinatorics.
Depending on time, we may also discuss relations to discrete Fourier analysis and property testing.
Mostly based on joint works with Amey Bhangale, Subhash Khot.
- Tags
-