Alladi Ramakrishnan Hall

Analysis of Algebraic Complexity Classes and Boolean Functions

Nitin Saurabh

HBNI PhD Viva Voce

In this talk I will present an overview of the work that went into my thesis. The talk will cover two different themes: Algebraic complexity theory, and Fourier-analysis of Boolean functions.

In the first part, we will look at completeness and reductions in algebraic complexity. In particular, we will see a characterisation of arithmetic classes using Homomorphism polynomials, and discuss about polynomial families that are of intermediate complexity.

In the second part, we will look at the Fourier-Entropy Influence Conjecture, and discuss possible approaches towards a solution of it.