How many processors are needed to compute a function in constant-time by a massively parallel algorithm? We consider this question with the lens of Boolean circuits. Here, we compose logic gates, acting as processors, with the number of layers corresponding to the running time, to compute a Boolean function.
Hence, the question we would like to answer is: how many gates do we need in such a circuit to compute a certain function if the circuit only has a constant number of layers? In particular, we are searching for explicit functions that require a very large number of gates, with a given set of choices for the logic gates.
Answers to such questions have implications in learning theory, cryptography, and the study of randomness. In this talk, I will discuss past and recent progress on such questions. Then, I will talk about a recent higher-order Fourier-analysis based approach, proposed by Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019), towards resolving a thirty-five years old conjecture. Afterwards, I will describe our contribution in developing this approach, where we propose studying the projection of an explicit set of vectors towards resolving this conjecture. The talk will conclude with some implications towards other frontiers in the study of Boolean circuits.

The work I will discuss in this talk was in collaboration with Prof. Sundar Vishwanathan at IIT Bombay.

Short Bio:

Vaibhav Krishan is a recent PhD graduate from IIT Bombay, where he worked under the supervision of Prof. Sundar Vishwanathan and Prof. Nutan Limaye. He has worked in the industry as a quantitative trader, and as a data scientist, after completing his undergrad.