DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2024.67

Agafonov’s Theorem for Probabilistic Selectors

Authors: Ulysse Léchine, Thomas Seiller, and Jakob Grue Simonsen

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

Abstract

A normal sequence over {0,1} is an infinite sequence for which every word of length k appears with frequency 2^{-k}. Agafonov’s eponymous theorem states that selection by a finite state selector preserves normality, i.e. if α is a normal sequence and A is a finite state selector, then the subsequence A(α) is either finite or a normal sequence. In this work, we address the following question: does this result hold when considering probabilistic selectors? We provide a partial positive answer, in the case where the probabilities involved are rational. More formally, we prove that given a normal sequence α and a rational probabilistic selector P, the selected subsequence P(α) will be a normal sequence with probability 1.

Cite as

Ulysse Léchine, Thomas Seiller, and Jakob Grue Simonsen. Agafonov’s Theorem for Probabilistic Selectors. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 67:1-67:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lechine_et_al:LIPIcs.MFCS.2024.67,
  author =	{L\'{e}chine, Ulysse and Seiller, Thomas and Simonsen, Jakob Grue},
  title =	{{Agafonov’s Theorem for Probabilistic Selectors}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{67:1--67: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.67},
  URN =		{urn:nbn:de:0030-drops-206238},
  doi =		{10.4230/LIPIcs.MFCS.2024.67},
  annote =	{Keywords: Normal sequences, probabilistic automata, Agafonov’s theorem}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2023.33

Revisiting Mulmuley: Simple Proof That Maxflow Is Not in the Algebraic Version of NC

Authors: Ulysse Léchine

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract

We give an alternate and simpler proof of the fact that PRAM without bit operations (shortened to iPRAM for integer PRAM) as considered in paper [Mulmuley, 1999] cannot solve the maxflow problem. To do so we consider the model of PRAM working over real number (rPRAM) which is at least as expressive as the iPRAM models when considering integer inputs. We then show that the rPRAM model is as expressive as the algebraic version of NC : algebraic circuits of fan-in 2 and of polylog depth noted NC^alg. We go on to show limitations of the NC^alg model using basic facts from real analysis : those circuits compute low degree piece wise polynomials. Then, using known results we show that the maxflow function is not a low-degree piece-wise polynomial. Finally we argue that NC^alg is actually a really limited class which limits our hope of extending our results to the boolean version of NC.

Cite as

Ulysse Léchine. Revisiting Mulmuley: Simple Proof That Maxflow Is Not in the Algebraic Version of NC. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 33:1-33:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lechine:LIPIcs.FSTTCS.2023.33,
  author =	{L\'{e}chine, Ulysse},
  title =	{{Revisiting Mulmuley: Simple Proof That Maxflow Is Not in the Algebraic Version of NC}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{33:1--33:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.33},
  URN =		{urn:nbn:de:0030-drops-194061},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.33},
  annote =	{Keywords: Algebraic complexity, P vs NC, algebraic NC, GCT program}
}

Search Results

Documents authored by Léchine, Ulysse

Agafonov’s Theorem for Probabilistic Selectors

Abstract

Cite as

Revisiting Mulmuley: Simple Proof That Maxflow Is Not in the Algebraic Version of NC

Abstract

Cite as

Thanks for your feedback!

Could not send message