seminar this monday

Skip to first unread message


Apr 19, 2024, 12:58:59 PMApr 19
to Kolmogorov seminar on complexity Date: April 22, 2024. Time: 18:30 (Moscow time), 17:30 (CET). Speaker: Ibragim Mamilov Title: Circuits for Majority -- generalizing the Valiant's construction

Valiant in 1984 gave a simple randomized construction of an $O(log n)$-depth monotone formula for the majority function. In fact, it was noticed later by different people that his argument actually gives an $O(log n)$-depth formula for Majority that only uses Maj_3 gates --majorities on 3 bits. In this talk, we will establish the following generalization -- Maj_n can be computed by an O(log_k n)-depth formula that only uses Maj_k gates, for every k and n. One simple application of this fact is that Maj_n can be computed by an unbounded fan-in polynomial-size O(log n / log log n)-depth monotone circuit, and this is tight due to the Razborov-Smolensky bound.

-- Saludos Sasha

Sent with Proton Mail secure email.


Apr 22, 2024, 10:35:57 AMApr 22
to Kolmogorov seminar on complexity

Just in case - 17:30 CEST (Central European ~Summer~ Time, like one that you have now if your are in France, for example)

Sent from Proton Mail Android

-------- Original Message --------
Вы получили это сообщение, поскольку подписаны на группу "Kolmogorov seminar on complexity".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке
Reply all
Reply to author
0 new messages