Talk 17 November (tomorrow)

[Daniil Musatov]

Dear participants, 

Tomorrow on the seminar there will be the final part of the presentation by Fyodor Kiselyov. We will discuss the definition of randomized reductions between search problems and some sort of "derandomization" result: any randomized reduction from PPP to some class may be transformed to a usual deterministic reduction.

The time of the seminar is as usual: 18:30 MSK and 16:30 CET.

The link is also the same: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

-- 

  See you tomorrow, 

  Daniil Musatov 

пн, 10 нояб. 2025 г., 10:13 Daniil Musatov <musa...@gmail.com>:

Dear participants, 

Today on the seminar there will be a continuation of the talk by Fyodor Kuselyov about classes of total search problems and (ir)reducibilities among them. The last time we talked about interrelations between white-box and black-box models. This time we will focus at the black-box model, and the talk will be almost independent of the first one. The plan of the talk is the following:

• Examples of reductions in black-box TFNP

• Definition and motivation of partial assignments

• Irreducibility of PPP to PLS

• Randomized reductions

• Presentation of a new result

[Alexander Shen]

https://youtu.be/WwX96fJuoug [ recording of part 2 (sorry for delay, I was traveling)

--
Вы получили это сообщение, поскольку подписаны на группу "Kolmogorov seminar on complexity".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес kolmogorov-seminar-on-...@googlegroups.com.
Чтобы посмотреть обсуждение, перейдите по ссылке https://groups.google.com/d/msgid/kolmogorov-seminar-on-complexity/CAMQnu%3DjTcE6Q2iwiNeaPAZJeW5Kq0Fxby3Kz6QmnG22LVA94Lg%40mail.gmail.com.