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

You may need the following programs to see the files

St. Petersburg Logic seminar
June 30, 2020 18:30, St. Petersburg, online

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

Yu. Gurevich

University of Michigan
 Materials: Adobe PDF 262.4 Kb

 Number of views: This page: 89 Materials: 4 Youtube Video:

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: