Search Results

Documents authored by S, Akhil


Document
RANDOM
One-Way Functions and Polynomial-Time Dimension

Authors: Satyadev Nandakumar, Subin Pulari, Akhil S, and Suronjona Sarma

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)


Abstract
The theory of randomness in computation has developed around several viewpoints on randomness and information, including statistical tests, compression schemes, betting strategies, and efficiently samplable sources. At the level of computability, several of these viewpoints turn out to be equivalent. A fundamental question is how robust these viewpoints remain when the underlying algorithms are subject to computational resource bounds. This paper studies this question for two polynomial-time notions of information density for infinite binary sequences. Polynomial-time dimension, denoted dim_P, quantifies information density using polynomial-time betting strategies called s-gales. Polynomial-time Kolmogorov complexity rate, denoted 𝒦_poly, gives a compression-based notion of polynomial-time information density using polynomial-time descriptions. Hitchcock and Vinodchandran (CCC 2004) showed that dim_P(X) ≥ 𝒦_poly(X) for every sequence X, and asked whether equality always holds. This question was later also posed by Stull. Our main result proves a duality between the non-robustness of these polynomial-time information-density notions and the existence of one-way functions. Assuming one-way functions exist, we construct a polynomial-time samplable distribution over infinite sequences such that, with probability 1, the sampled sequence X satisfies dim_P(X) > 𝒦_poly(X) by a uniform gap. Conversely, we show that if some polynomial-time samplable distribution yields such an almost-sure uniform separation, then infinitely-often one-way functions exist. Thus, separations between these two polynomial-time information-density notions over efficiently samplable sources lie at the same frontier as one-way functions, with the reverse direction yielding infinitely-often one-way functions. This duality gives a negative answer, assuming one-way functions, to the open question posed by Hitchcock, Vinodchandran, and Stull. Furthermore, we show that there are individual sequences witnessing separations between dim_P and 𝒦_poly, and that the gap can be made arbitrarily close to 1. We also establish analogous bounds for strong polynomial-time dimension and asymptotic upper polynomial-time Kolmogorov complexity rates. The main technical challenge is to connect finite-length pseudorandomness assumptions with asymptotic information-density measures on infinite sequences. Our proof addresses this by developing several new constructions and arguments involving probabilistic tools such as the Borel-Cantelli lemma, Kolmogorov’s inequality for martingales, and techniques for approximating probabilities of efficiently samplable distributions. The work shows that the question of non-robustness for polynomial-time information-density notions, which is prima facie different from standard questions about randomness, pseudorandomness, and cryptography, is in fact intimately related to the existence of one-way functions.

Cite as

Satyadev Nandakumar, Subin Pulari, Akhil S, and Suronjona Sarma. One-Way Functions and Polynomial-Time Dimension. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 44:1-44:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{nandakumar_et_al:LIPIcs.APPROX/RANDOM.2026.44,
  author =	{Nandakumar, Satyadev and Pulari, Subin and S, Akhil and Sarma, Suronjona},
  title =	{{One-Way Functions and Polynomial-Time Dimension}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{44:1--44:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.44},
  URN =		{urn:nbn:de:0030-drops-277619},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.44},
  annote =	{Keywords: Polynomial-time dimension, One-way functions, Resource bounded randomness, Kolmogorov complexity, Polynomial-time martingales}
}
Document
Finite-State Dimension for Continued Fractions: Betting, Entropy and Normality

Authors: Satyadev Nandakumar, Subin Pulari, and Akhil S

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)


Abstract
Finite-state dimension quantifies the asymptotic density of information in an infinite sequence as seen by finite automata, and can be viewed as a bounded-memory analogue of Hausdorff dimension. The theory is by now well developed for base-b expansions. In this paper we initiate the study of finite-state dimension in the setting of continued fractions. This setting brings several new difficulties. The natural reference measure is the Gauss measure, which is the canonical invariant probability measure for the Gauss transformation governing the continued fraction shift. Unlike in the base-b setting, however, this measure is not a product measure. In addition, the digit space is inherently infinite, so the symbolic setting is markedly less rigid than the usual finite-alphabet framework. Continued fraction analogues of effective dimension have received considerable attention in recent years, but a finite-state theory in this setting has so far been missing. Finite-state dimension in the classical setting admits several equivalent formulations. We begin from the original finite-state s-gale viewpoint. In the continued fraction setting, however, the betting odds are no longer fixed in advance: unlike in the base-b case, the fair payoff for the next symbol is determined by conditional Gauss probabilities, and these vary with the current continued fraction cylinder. This makes the choice of a finite-state betting model genuinely nontrivial. We first examine a natural local finite-state betting model for truncated continued fraction digits, in which a gambler may use both the visible local context and an additional finite internal memory. We show that this model is too strong: there is a fixed finite-state gambler that wins at a positive exponential rate on every continued fraction normal point. Consequently, full dimension in this model does not characterize continued fraction normality, and the classical Schnorr-Stimm dichotomy fails. We then isolate the source of this failure and introduce a restricted context-gambler model in which the gambler is allowed to use only the visible truncated context, with no additional hidden finite-state memory. For this restricted model, we obtain, in direct analogy with the base-b setting, an entropy-rate characterization of finite-state dimension in terms of conditional entropy rates, and from this derive an exact finite-state characterization of continued fraction normality: an irrational real has finite-state dimension 1 if and only if its continued fraction expansion is normal. Finally, we prove that the Schnorr-Stimm dichotomy does hold in this restricted setting: on a continued fraction normal point every such gambler either preserves constant capital or loses at an exponential rate, while on every non-normal point some such gambler wins at an exponential rate.

Cite as

Satyadev Nandakumar, Subin Pulari, and Akhil S. Finite-State Dimension for Continued Fractions: Betting, Entropy and Normality. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{nandakumar_et_al:LIPIcs.MFCS.2026.39,
  author =	{Nandakumar, Satyadev and Pulari, Subin and S, Akhil},
  title =	{{Finite-State Dimension for Continued Fractions: Betting, Entropy and Normality}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.39},
  URN =		{urn:nbn:de:0030-drops-274208},
  doi =		{10.4230/LIPIcs.MFCS.2026.39},
  annote =	{Keywords: Finite-state dimension, continued fractions, normality, finite-state gamblers, entropy rates}
}
Document
Randomness Extraction Fails for Finite-State Dimension

Authors: Subin Pulari and Akhil S

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)


Abstract
Finite-state dimension, introduced as a finite-state analogue of Hausdorff dimension, quantifies the lower asymptotic density of information in an infinite sequence as perceived by finite-state automata. It admits several equivalent formulations; two particularly useful are via finite-state gambling strategies and via the optimal asymptotic compression ratio achieved by information-lossless finite-state compressors. Normal sequences represent the highest level of algorithmic randomness visible to finite automata, and are exactly those sequences having finite-state dimension equal to 1. This motivates a bounded-memory notion of randomness extraction: can a finite-state transducer, reading a single sequence streamingly, extract a normal output from a single input source? More modestly, can it always transform the input into an output of strictly higher finite-state dimension? Finite-state transducers can perform surprisingly effective one-pass transformations: even with constant memory they can implement variable-length coding schemes including Shannon-Fano coding, remove local redundancy, and increase the apparent randomness rate on many structured or stochastic inputs. We show randomness extraction using transducers is impossible in a strong, explicit form. For every rational s ∈ (0,1), we construct a near linear-time computable binary sequence X with dim_FS(X) = s such that for every finite-state transducer T, the output satisfies dim_FS(T(X)) ≤ s. Thus, for these sequences, finite-state transduction cannot extract normality - indeed it cannot even improve finite-state dimension. Our proof proceeds by a structural analysis of finite-state transducers together with a dimension-preserving diagonal construction that, for each target s, builds a sequence whose organization defeats every such transducer’s attempt to concentrate randomness. The result is a finite-state analogue of Miller’s non-extractability phenomenon for effective dimension, but its proof relies on substantially different techniques, tailored to the finite-state setting. Furthermore, we show that the impossibility persists even with multiple independent input streams. We treat two notions of independence: (i) Kolmogorov-complexity–based independence (via joint prefix complexity), and (ii) a finite-state notion of relative independence, formulated via relative finite-state dimension. By sharp contrast with the effective-dimension setting - where two independent sources suffice for a uniform effective procedure that boosts randomness rate arbitrarily close to 1 - we show that finite-state dimension exhibits no comparable multi-source extraction phenomenon. Specifically, for every rational s ∈ (0,1) and every fixed k ≥ 2, there exist k independent sources, each of finite-state dimension s, such that for every k-input finite-state transducer T, the output satisfies dim_FS(T(X_1,… ,X_k)) ≤ s. Thus, even independent streams do not allow bounded-memory transduction to output a normal sequence or to increase finite-state dimension.

Cite as

Subin Pulari and Akhil S. Randomness Extraction Fails for Finite-State Dimension. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 78:1-78:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{pulari_et_al:LIPIcs.LICS.2026.78,
  author =	{Pulari, Subin and S, Akhil},
  title =	{{Randomness Extraction Fails for Finite-State Dimension}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{78:1--78:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.78},
  URN =		{urn:nbn:de:0030-drops-268656},
  doi =		{10.4230/LIPIcs.LICS.2026.78},
  annote =	{Keywords: Finite-state dimension, normal numbers, randomness extraction, finite-state transducers}
}
Document
Point-To-Set Principle and Constructive Dimension Faithfulness

Authors: Satyadev Nandakumar, Subin Pulari, and Akhil S

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)


Abstract
Hausdorff Φ-dimension is a notion of Hausdorff dimension developed using a restricted class of coverings of a set. We introduce a constructive analogue of Φ-dimension using the notion of constructive Φ-s-supergales. We prove a Point-to-Set Principle for Φ-dimension, through which we get Point-to-Set Principles for Hausdorff dimension, continued-fraction dimension and dimension of Cantor coverings as special cases. We also provide a Kolmogorov complexity characterization of constructive Φ-dimension. A class of covering sets Φ is said to be "faithful" to Hausdorff dimension if the Φ-dimension and Hausdorff dimension coincide for every set. Similarly, Φ is said to be "faithful" to constructive dimension if the constructive Φ-dimension and constructive dimension coincide for every set. Using the Point-to-Set Principle for Cantor coverings and a new technique for the construction of sequences satisfying a certain Kolmogorov complexity condition, we show that the notions of "faithfulness" of Cantor coverings at the Hausdorff and constructive levels are equivalent. We adapt the result by Albeverio, Ivanenko, Lebid, and Torbin [Albeverio et al., 2020] to derive the necessary and sufficient conditions for the constructive dimension faithfulness of the coverings generated by the Cantor series expansion, based on the terms of the expansion.

Cite as

Satyadev Nandakumar, Subin Pulari, and Akhil S. Point-To-Set Principle and Constructive Dimension Faithfulness. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 76:1-76:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{nandakumar_et_al:LIPIcs.MFCS.2024.76,
  author =	{Nandakumar, Satyadev and Pulari, Subin and S, Akhil},
  title =	{{Point-To-Set Principle and Constructive Dimension Faithfulness}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{76:1--76:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.76},
  URN =		{urn:nbn:de:0030-drops-206321},
  doi =		{10.4230/LIPIcs.MFCS.2024.76},
  annote =	{Keywords: Kolmogorov complexity, Constructive dimension, Faithfulness, Point to set principle, Continued fraction dimension, Cantor series expansion}
}
Document
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.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}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail