Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Calendar
Search
Add a seminar

RSS
Forthcoming seminars




Kolmogorov seminar on computational complexity and descriptive complexity
March 18, 2013 16:45–18:25, Moscow
 


Algorithmic statistics

A. Kh. Shen'

Number of views:
This page:227

Abstract: The quantity of information in a word is measured by its Kolmogorov complexity. But not all words with the same Kolmogorov complexity have the same properties. Beyond complexity, there are some "information" characteristics of a word. These characteristics can be represented not as a single number but rather as a curve: how fast the complexity increase when we bound the time of computation; or, which two-parts descriptions exist for this word; or, how close to the end of the list we put our word while enumerating all words of complexity at most N, etc.
We suppose to survey the basic and simple results and discuss in more detail some more involved ones (by works of Vereshchagin, Vitanyi, gacs, tromp, Antunes, etc.)
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024