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