EDBT 2026 Demo / reviewers in the wild / expert
Prateek Vishnoi
dblp:272/6920
· DBLP profile ↗
4ranked-venue papers
1as first author
3since 2021 · last 2023
0000-0003-0575-0655ORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 4 · 1 first-author · 3 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2023 | Effective Continued Fraction Dimension Versus Effective Hausdorff Dimension of RealsabstractWe 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. Satyadev Nandakumar, Akhil S, Prateek Vishnoi |
MFCS | 3 |
| 2022 | Normality, Randomness and Kolmogorov Complexity of Continued Fractions
Prateek Vishnoi |
TAMC | 1 |
| 2022 | On continued fraction randomness and normality
Satyadev Nandakumar, Prateek Vishnoi |
Inf. Comput. | 2 |
| 2020 | Randomness and Effective Dimension of Continued FractionsabstractRecently, 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. Satyadev Nandakumar, Prateek Vishnoi |
MFCS | 2 |