Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Forthcoming seminars
Seminar calendar
List of seminars
Archive by years
Register a seminar

Search
RSS
Forthcoming seminars






Seminar of the Laboratory of Mathematical Logic (Saint Petersburg)
June 30, 2020 18:30, Saint Petersburg, online
 


What, if anything, can be done in linear time?

Yu. Gurevich

University of Michigan
Video records:
MP4 109.1 Mb
Materials:
Adobe PDF 262.4 Kb

Number of views:
This page:193
Video files:25
Materials:15
Youtube Video:

Yu. Gurevich


Видео не загружается в Ваш браузер:
  1. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  2. Сообщите администратору портала о данной ошибке



Abstract: The answer to the title question seems to be “Not much.” Even sorting $n$ items takes $n \times \log ( n )$ swaps. But, in fact, quite a bit can be done in linear time. We start with an illustration of linear-time techniques. Then we sketch the linear-time decision algorithm for propositional primal infon logic. Finally we mention useful extensions of that logic decidable in deterministic or probabilistic linear time.

Materials: gurevich_spb_2020_slides.pdf (262.4 Kb)

Language: English

SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Contact us:
 Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2021