Computer Science/Discrete Mathematics Seminar II

The Lens of Abelian Embeddings

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.

Date & Time

March 28, 2023 | 10:30am – 12:30pm

Location

Simonyi Hall 101 and Remote Access

Affiliation

Massachusetts Institute of Technology