Constructions of circuits for the majority function.

Abstract: 

We will consider a task of computing the majority function by Boolean circuits. This function has logarithmic-depth circuits. Moreover, this remains true when circuits consist of just binary AND and OR, no negations. However, in this regime, no simultaneously explicit and “simple” construction is known (with “simple” being an informal property, referencing a subjective expositional complexity of a construction). In the talk, I will present a small piece of progress towards getting such a construction, and I will probably explain some classical constructions along the way.

Posted on Sep 23, 2024 in ACGO, Seminars