Ibragim Mamilov. Maj_n (majority of n) computed by Maj_k-circuit with clog_k n depth (22.4.2024)

Kolmogorov seminar on computational and descriptional complexity (founded by Kolmogorov around 1979); talk by Ibragim Mamilov.
A well known probabilistic construction of Valiant (majority of n bits, using only AND and OR of arity 2, log depth) labels vertices of Maj_3 full tree by random variables and shows that probability of error becomes smaller than 2^{-n} after O(\log n) layers. The same construction can be performed with Maj_k elements, but the probability estimate becomes more tricky.