BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/4
DTSTAMP:20230914T125905Z
SUMMARY:Dynamics\, Measure\, and Dimension in the Theory of Computing
DESCRIPTION:Speaker: Satyadev Nandakumar\nDepartment of Computer Science\nI
 owa State University\nUnited States of America\nhttp://www.c\n\nAbstract: 
 \nMy talk focuses on two aspects of my thesis\, in the theory of algorithm
 ic randomness. \n\nThe first result relates to the finite-state compressib
 ility of infinite sequences. If $s$ is a real number in the unit interval 
 and $q$ is a non-zero rational represented in base-$k$ notation\, we show 
 that their product ($q \\\\bmod 1$) represented in base-$k$\, has exactly 
 the same finite-state compressibility as $s$. This result has applications
  to a classical area in mathematics\, the theory of normal numbers. It gen
 eralizes and provides a new proof of Wall's classical result that multipli
 cation with a non-zero rational preserves normality of a number. This part
  of the talk provides a brief overview of the tools used to prove this res
 ult\, namely\, Schur concavity and majorization.\n\nThe second part of the
  talk focuses on a result in the theory of algorithmic randomness. One of 
 the major initial successes in this theory was Martin-L\\\\ {o}f's use of 
 computability theory to give the formal definition of an individual random
  sequence. In this theory\, we try to prove effective versions of probabil
 istic laws. We attempt to establish that classical laws which hold with pr
 obability 1\, indeed hold for every random sequence. This version of a the
 orem is stronger and has more intuitive content\, since it justifies our b
 elief that a random sequence passes most tests of randomness embodied in p
 robablistic laws.\n\nBirkhoff's Ergodic Theorem is a famous probabilistic 
 law that was widely believed to resist effectivization. However\, V'yugin 
 proved an effective version of the Ergodic theorem based on Bishop's const
 ructive version of the theorem. V'yugin's theorem has limited applications
 \, however\, since he assumes that the random variables are computable\, h
 ence continuous. Braverman in a recent work introduced a notion termed `gr
 aph computability' to deal with discontinuous functions. In this part of t
 he talk\, we extend his theorem to hold for a suitable restriction of grap
 h-computable functions. We also discuss some applications of this theorem 
 to continued fractions.\n
URL:https://www.tcs.tifr.res.in/web/events/4
DTSTART;VALUE=DATE:20090611
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR