6 Search Results for "Nandakumar, Satyadev"

Document
DOI: 10.4230/LIPIcs.MFCS.2023.65
A Weyl Criterion for Finite-State Dimension and Applications

Authors: Jack H. Lutz, Satyadev Nandakumar, and Subin Pulari

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Finite-state dimension, introduced early in this century as a finite-state version of classical Hausdorff dimension, is a quantitative measure of the lower asymptotic density of information in an infinite sequence over a finite alphabet, as perceived by finite automata. Finite-state dimension is a robust concept that now has equivalent formulations in terms of finite-state gambling, lossless finite-state data compression, finite-state prediction, entropy rates, and automatic Kolmogorov complexity. The 1972 Schnorr-Stimm dichotomy theorem gave the first automata-theoretic characterization of normal sequences, which had been studied in analytic number theory since Borel defined them in 1909. This theorem implies, in present-day terminology, that a sequence (or a real number having this sequence as its base-b expansion) is normal if and only if it has finite-state dimension 1. One of the most powerful classical tools for investigating normal numbers is the 1916 Weyl’s criterion, which characterizes normality in terms of exponential sums. Such sums are well studied objects with many connections to other aspects of analytic number theory, and this has made use of Weyl’s criterion especially fruitful. This raises the question whether Weyl’s criterion can be generalized from finite-state dimension 1 to arbitrary finite-state dimensions, thereby making it a quantitative tool for studying data compression, prediction, etc. i.e., Can we characterize all compression ratios using exponential sums?. This paper does exactly this. We extend Weyl’s criterion from a characterization of sequences with finite-state dimension 1 to a criterion that characterizes every finite-state dimension. This turns out not to be a routine generalization of the original Weyl criterion. Even though exponential sums may diverge for non-normal numbers, finite-state dimension can be characterized in terms of the dimensions of the subsequence limits of the exponential sums. In case the exponential sums are convergent, they converge to the Fourier coefficients of a probability measure whose dimension is precisely the finite-state dimension of the sequence. This new and surprising connection helps us bring Fourier analytic techniques to bear in proofs in finite-state dimension, yielding a new perspective. We demonstrate the utility of our criterion by substantially improving known results about preservation of finite-state dimension under arithmetic. We strictly generalize the results by Aistleitner and Doty, Lutz and Nandakumar for finite-state dimensions under arithmetic operations. We use the method of exponential sums and our Weyl criterion to obtain the following new result: If y is a number having finite-state strong dimension 0, then dim_FS(x+qy) = dim_FS(x) and Dim_FS(x+qy) = Dim_FS(x) for any x ∈ ℝ and q ∈ ℚ. This generalization uses recent estimates obtained in the work of Hochman [Hochman, 2014] regarding the entropy of convolutions of probability measures.
Cite as

Jack H. Lutz, Satyadev Nandakumar, and Subin Pulari. A Weyl Criterion for Finite-State Dimension and Applications. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 65:1-65:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lutz_et_al:LIPIcs.MFCS.2023.65,
  author =	{Lutz, Jack H. and Nandakumar, Satyadev and Pulari, Subin},
  title =	{{A Weyl Criterion for Finite-State Dimension and Applications}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{65:1--65:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.65},
  URN =		{urn:nbn:de:0030-drops-185997},
  doi =		{10.4230/LIPIcs.MFCS.2023.65},
  annote =	{Keywords: Finite-state dimension, Finite-state compression, Weyl’s criterion, Exponential sums, Normal numbers}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.70
Effective Continued Fraction Dimension Versus Effective Hausdorff Dimension of Reals

Authors: Satyadev Nandakumar, Akhil S, and Prateek Vishnoi

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We establish that constructive continued fraction dimension originally defined using s-gales [Nandakumar and Vishnoi, 2022] is robust, but surprisingly, that the effective continued fraction dimension and effective (base-b) Hausdorff dimension of the same real can be unequal in general. We initially provide an equivalent characterization of continued fraction dimension using Kolmogorov complexity. In the process, we construct an optimal lower semi-computable s-gale for continued fractions. We also prove new bounds on the Lebesgue measure of continued fraction cylinders, which may be of independent interest. We apply these bounds to reveal an unexpected behavior of continued fraction dimension. It is known that feasible dimension is invariant with respect to base conversion [Hitchcock and Mayordomo, 2013]. We also know that Martin-Löf randomness and computable randomness are invariant not only with respect to base conversion, but also with respect to the continued fraction representation [Nandakumar and Vishnoi, 2022]. In contrast, for any 0 < ε < 0.5, we prove the existence of a real whose effective Hausdorff dimension is less than ε, but whose effective continued fraction dimension is greater than or equal to 0.5. This phenomenon is related to the "non-faithfulness" of certain families of covers, investigated by Peres and Torbin [Peres and Torbin] and by Albeverio, Ivanenko, Lebid and Torbin [Albeverio et al., 2020]. We also establish that for any real, the constructive Hausdorff dimension is at most its effective continued fraction dimension.
Cite as

Satyadev Nandakumar, Akhil S, and Prateek Vishnoi. Effective Continued Fraction Dimension Versus Effective Hausdorff Dimension of Reals. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 70:1-70:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{nandakumar_et_al:LIPIcs.MFCS.2023.70,
  author =	{Nandakumar, Satyadev and S, Akhil and Vishnoi, Prateek},
  title =	{{Effective Continued Fraction Dimension Versus Effective Hausdorff Dimension of Reals}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{70:1--70:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.70},
  URN =		{urn:nbn:de:0030-drops-186041},
  doi =		{10.4230/LIPIcs.MFCS.2023.70},
  annote =	{Keywords: Algorithmic information theory, Kolmogorov complexity, Continued fractions, Effective Hausdorff dimension}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.48
Real Numbers Equally Compressible in Every Base

Authors: Satyadev Nandakumar and Subin Pulari

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
This work solves an open question in finite-state compressibility posed by Lutz and Mayordomo [Lutz and Mayordomo, 2021] about compressibility of real numbers in different bases. Finite-state compressibility, or equivalently, finite-state dimension, quantifies the asymptotic lower density of information in an infinite sequence. Absolutely normal numbers, being finite-state incompressible in every base of expansion, are precisely those numbers which have finite-state dimension equal to 1 in every base. At the other extreme, for example, every rational number has finite-state dimension equal to 0 in every base. Generalizing this, Lutz and Mayordomo in [Lutz and Mayordomo, 2021] (see also Lutz [Lutz, 2012]) posed the question: are there numbers which have absolute positive finite-state dimension strictly between 0 and 1 - equivalently, is there a real number ξ and a compressibility ratio s ∈ (0,1) such that for every base b, the compressibility ratio of the base-b expansion of ξ is precisely s? It is conceivable that there is no such number. Indeed, some works explore "zero-one" laws for other feasible dimensions [Fortnow et al., 2011] - i.e. sequences with certain properties either have feasible dimension 0 or 1, taking no value strictly in between. However, we answer the question of Lutz and Mayordomo affirmatively by proving a more general result. We show that given any sequence of rational numbers ⟨q_b⟩_{b=2}^∞, we can explicitly construct a single number ξ such that for any base b, the finite-state dimension/compression ratio of ξ in base-b is q_b. As a special case, this result implies the existence of absolutely dimensioned numbers for any given rational dimension between 0 and 1, as posed by Lutz and Mayordomo. In our construction, we combine ideas from Wolfgang Schmidt’s construction of absolutely normal numbers from [Schmidt, 1961], results regarding low discrepancy sequences and several new estimates related to exponential sums.
Cite as

Satyadev Nandakumar and Subin Pulari. Real Numbers Equally Compressible in Every Base. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 48:1-48:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{nandakumar_et_al:LIPIcs.STACS.2023.48,
  author =	{Nandakumar, Satyadev and Pulari, Subin},
  title =	{{Real Numbers Equally Compressible in Every Base}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{48:1--48:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.48},
  URN =		{urn:nbn:de:0030-drops-177008},
  doi =		{10.4230/LIPIcs.STACS.2023.48},
  annote =	{Keywords: Finite-state dimension, Finite-state compression, Absolutely dimensioned numbers, Exponential sums, Weyl criterion, Normal numbers}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.80
Ergodic Theorems and Converses for PSPACE Functions

Authors: Satyadev Nandakumar and Subin Pulari

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We initiate the study of effective pointwise ergodic theorems in resource-bounded settings. Classically, the convergence of the ergodic averages for integrable functions can be arbitrarily slow [Ulrich Krengel, 1978]. In contrast, we show that for a class of PSPACE L¹ functions, and a class of PSPACE computable measure-preserving ergodic transformations, the ergodic average exists and is equal to the space average on every EXP random. We establish a partial converse that PSPACE non-randomness can be characterized as non-convergence of ergodic averages. Further, we prove that there is a class of resource-bounded randoms, viz. SUBEXP-space randoms, on which the corresponding ergodic theorem has an exact converse - a point x is SUBEXP-space random if and only if the corresponding effective ergodic theorem holds for x.
Cite as

Satyadev Nandakumar and Subin Pulari. Ergodic Theorems and Converses for PSPACE Functions. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 80:1-80:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{nandakumar_et_al:LIPIcs.MFCS.2021.80,
  author =	{Nandakumar, Satyadev and Pulari, Subin},
  title =	{{Ergodic Theorems and Converses for PSPACE Functions}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{80:1--80:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.80},
  URN =		{urn:nbn:de:0030-drops-145204},
  doi =		{10.4230/LIPIcs.MFCS.2021.80},
  annote =	{Keywords: Ergodic Theorem, Resource-bounded randomness, Computable analysis, Complexity theory}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.73
Randomness and Effective Dimension of Continued Fractions

Authors: Satyadev Nandakumar and Prateek Vishnoi

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Recently, Scheerer [Adrian-Maria Scheerer, 2017] and Vandehey [Vandehey, 2016] showed that normality for continued fraction expansions and base-b expansions are incomparable notions. This shows that at some level, randomness for continued fractions and binary expansion are different statistical concepts. In contrast, we show that the continued fraction expansion of a real is computably random if and only if its binary expansion is computably random. To quantify the degree to which a continued fraction fails to be effectively random, we define the effective Hausdorff dimension of individual continued fractions, explicitly constructing continued fractions with dimension 0 and 1.
Cite as

Satyadev Nandakumar and Prateek Vishnoi. Randomness and Effective Dimension of Continued Fractions. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 73:1-73:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nandakumar_et_al:LIPIcs.MFCS.2020.73,
  author =	{Nandakumar, Satyadev and Vishnoi, Prateek},
  title =	{{Randomness and Effective Dimension of Continued Fractions}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{73:1--73:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.73},
  URN =		{urn:nbn:de:0030-drops-127424},
  doi =		{10.4230/LIPIcs.MFCS.2020.73},
  annote =	{Keywords: Continued fractions, Martin-L\"{o}f randomness, Computable randomness, effective Fractal dimension}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.221
Dimension, Pseudorandomness and Extraction of Pseudorandomness

Authors: Manindra Agrawal, Diptarka Chakraborty, Debarati Das, and Satyadev Nandakumar

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract
In this paper we propose a quantification of distributions on a set of strings, in terms of how close to pseudorandom a distribution is. The quantification is an adaptation of the theory of dimension of sets of infinite sequences introduced by Lutz. Adapting Hitchcock's work, we also show that the logarithmic loss incurred by a predictor on a distribution is quantitatively equivalent to the notion of dimension we define. Roughly, this captures the equivalence between pseudorandomness defined via indistinguishability and via unpredictability. Later we show some natural properties of our notion of dimension. We also do a comparative study among our proposed notion of dimension and two well known notions of computational analogue of entropy, namely HILL-type pseudo min-entropy and next-bit pseudo Shannon entropy. Further, we apply our quantification to the following problem. If we know that the dimension of a distribution on the set of n-length strings is s in (0,1], can we extract out O(sn) pseudorandom bits out of the distribution? We show that to construct such extractor, one need at least Omega(log n) bits of pure randomness. However, it is still open to do the same using O(log n) random bits. We show that deterministic extraction is possible in a special case - analogous to the bit-fixing sources introduced by Chor et al., which we term nonpseudorandom bit-fixing source. We adapt the techniques of Gabizon, Raz and Shaltiel to construct a deterministic pseudorandom extractor for this source. By the end, we make a little progress towards P vs. BPP problem by showing that existence of optimal stretching function that stretches O(log n) input bits to produce n output bits such that output distribution has dimension s in (0,1], implies P=BPP.
Cite as

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, and Satyadev Nandakumar. Dimension, Pseudorandomness and Extraction of Pseudorandomness. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 221-235, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.FSTTCS.2015.221,
  author =	{Agrawal, Manindra and Chakraborty, Diptarka and Das, Debarati and Nandakumar, Satyadev},
  title =	{{Dimension, Pseudorandomness and Extraction of Pseudorandomness}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{221--235},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.221},
  URN =		{urn:nbn:de:0030-drops-56184},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.221},
  annote =	{Keywords: Pseudorandomness, Dimension, Martingale, Unpredictability, Pseudoentropy, Pseudorandom Extractor, Hard Function}
}
  • Refine by Author
  • 6 Nandakumar, Satyadev
  • 3 Pulari, Subin
  • 2 Vishnoi, Prateek
  • 1 Agrawal, Manindra
  • 1 Chakraborty, Diptarka
  • Show More...

  • Refine by Classification
  • 3 Mathematics of computing → Information theory
  • 2 Theory of computation → Computability
  • 2 Theory of computation → Constructive mathematics
  • 1 Mathematics of computing → Probability and statistics
  • 1 Theory of computation → Complexity theory and logic

  • Refine by Keyword
  • 2 Continued fractions
  • 2 Exponential sums
  • 2 Finite-state compression
  • 2 Finite-state dimension
  • 2 Normal numbers
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2023
  • 1 2015
  • 1 2020
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact