Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)
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)
@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}
}
Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)
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)
@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}
}
Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)
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)
@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}
}
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
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)
@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}
}
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
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)
@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}
}