Project Presentation: Two Problems Related to Small-set Expansion and Reed-Muller Codes.

Arghya Chakraborty
Friday, 11 Oct 2019, 18:15 to 19:15
A-201 (STCS Seminar Room)
Abstract: This talk will comprise of two parts. In the first half, I shall discuss about Reed-Muller Codes and Reed-Solomon Codes. Basically, we shall prove that Reed-Muller Codes are a subset of Reed-Solomon Codes. The next half will be a discussion on small set expansion, norm bounds and hypercontractivity. Small set expansion is a notion weaker than expansion requirining just the small sets to be expanding. Hypercontractivity is a property of and operator and here we shall mostly be looking at hypercontractivity of the adjacency matrix but only corresponding to the top eigenspace. Norm bounds are properties of a vector space and here we shall consider norm bounds on the top eigenspace of the adjacency matrix. We shall look at which of the three are equivalent notions and which are not.