seminar this monday

[kozmath]

https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09 Date: April 22, 2024. Time: 18:30 (Moscow time), 17:30 (CET). Speaker: Ibragim Mamilov Title: Circuits for Majority -- generalizing the Valiant's construction

Abstract:

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.

[kozmath]

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".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес kolmogorov-seminar-on-...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/kolmogorov-seminar-on-complexity/Zjh5kWPjEBhPA_nBIMs-4zFkYGd-bdnDMI4predcUL6uNx8iIBKgUiPiO7DZ4V4qoBrBLWiFHacRH1zvWL9isKwrMFajzAvHOfFWONb_tCY%3D%40proton.me.