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.