Document Open Access Logo

Polynomial-Time Rademacher Theorem, Porosity and Randomness

Author Alex Galicki

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.30.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Alex Galicki

Cite As Get BibTex

Alex Galicki. Polynomial-Time Rademacher Theorem, Porosity and Randomness. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.30

Abstract

The main result of this paper is a polynomial time version of Rademacher's theorem. We show that if z is p-random, then every polynomial time computable Lipschitz function f:R^n->R is differentiable at z. This is a generalization of the main result of [Nies, STACS2014].
		
To prove our main result, we introduce and study a new notion, p-porosity, and prove several results of independent interest. In particular, we characterize p-porosity in terms of polynomial time computable martingales and we show that p-randomness in R^n is invariant under polynomial time computable linear isometries.

Subject Classification

Keywords
  • Rademacher
  • porosity
  • p-randomness
  • differentiability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. G. Petruska A. M. Bruckner, M. Laczkovich and B. S. Thomson. Porosity and approximate derivatives. Canadian Journal of Mathematics, 38:1149-1180, 1986. URL: http://dx.doi.org/10.4153/CJM-1986-058-7.
  2. K. Ambos-Spies, H. Fleischhack, and H. Huwig. P-generic sets, pages 58-68. Springer Berlin Heidelberg, 1984. URL: http://dx.doi.org/10.1007/3-540-13345-3_5.
  3. K. Ambos-Spies, H. Fleischhack, and H. Huwig. Diagonalizations over polynomial time computable sets. Theoretical Computer Science, 51(1):177-204, 1987. URL: http://dx.doi.org/10.1016/0304-3975(87)90053-3.
  4. K. Ambos-Spies, S. A. Terwijn, and Z. Xizhong. Resource bounded randomness and weakly complete problems, pages 369-377. Springer Berlin Heidelberg, 1994. URL: http://dx.doi.org/10.1007/3-540-58325-4_201.
  5. D. N. Bessis and F. H. Clarke. Partial subdifferentials, derivatives and Rademacher’s theorem. Transactions of AMS, 351(7):2899-2926, 1999. Google Scholar
  6. Miller J. Bienvenu L., Hölzl R. and Nies A. Denjoy, Demuth and density. Journal of Mathematical Logic, 14(01):1450004, 2014. URL: http://dx.doi.org/10.1142/S0219061314500044.
  7. J. M. Borwein and X. Wang. Cone-monotone functions: Differentiability and continuity. Canadian Journal of Mathematics, 57:961-982, 2005. URL: http://dx.doi.org/10.4153/CJM-2005-037-5.
  8. V. Brattka, J. Miller, and A. Nies. Randomness and differentiability. Transactions of the AMS, 368:581-605, 2016. arXiv version at arxiv.org/abs/1104.4465. Google Scholar
  9. A. M. Bruckner and B. S. Thomson. Porosity estimates for the Dini derivatives. Real Anal. Exch., 9:508-538, 1984. Google Scholar
  10. R. Downey and D. Hirschfeldt. Algorithmic randomness and complexity. Springer-Verlag, Berlin, 2010. 855 pages. Google Scholar
  11. R. G. Downey and D. R. Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, 2010. Google Scholar
  12. Stephen A. Fenner. Functions that preserve p-randomness. Inf. Comput., 231:125-142, October 2013. URL: http://dx.doi.org/10.1016/j.ic.2013.08.009.
  13. C. Freer, B. Kjos-Hanssen, A. Nies, and F. Stephan. Algorithmic aspects of Lipschitz functions. Computability, 3(1):45-61, 2014. URL: http://dx.doi.org/10.3233/COM-14025.
  14. A. Galicki. Randomness and Differentiability of Convex Functions, pages 196-205. Springer International Publishing, Cham, 2015. URL: http://dx.doi.org/10.1007/978-3-319-20028-6_20.
  15. A. Galicki. Effective Brenier Theorem: Applications to Computable Analysis and Algorithmic Randomness. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS'16, pages 720-729, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2933575.2933596.
  16. M. Khan. Lebesgue density and ∏₁⁰ classes. Journal of Symbolic Logic, 81(1):80-95, 2016. Google Scholar
  17. Ker-I Ko. Complexity theory of real functions. Birkhauser Boston Inc., 1991. Google Scholar
  18. A. Nies. Computability and randomness, volume 51 of Oxford Logic Guides. Oxford University Press, Oxford, 2009. URL: http://dx.doi.org/10.1093/acprof:oso/9780199230761.001.0001.
  19. André Nies. Differentiability of polynomial time computable functions. In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pages 602-613, Dagstuhl, Germany, 2014. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2014.602.
  20. N. Pathak, C. Rojas, and S. G. Simpson. Schnorr randomness and the Lebesgue differentiation theorem. Proc. Amer. Math. Soc., 142(1):335-349, 2014. URL: http://dx.doi.org/10.1090/S0002-9939-2013-11710-7.
  21. D. Preiss and L. Zajíček. Directional derivatives of lipschitz functions. Israel Journal of Mathematics, 125(1):1-27, 2001. URL: http://dx.doi.org/10.1007/BF02773371.
  22. J. Lindenstrauss, D. Preiss and J. Tišer. Fréchet Differentiability of Lipschitz Functions and Porous Sets in Banach Spaces. Annals of Mathematics Studies. Princeton University Press, 2012. Google Scholar
  23. H. Rademacher. Über partielle und totale Differenzierbarkeit von Funktionen mehrerer Variabeln und über die Transformation der Doppelintegrale. Math. Ann., 79(1):340-359, 1919. Google Scholar
  24. O. Tapiola. Random and non-random dyadic systems in doubling metric spaces, 2012. MSc thesis. URL: http://hdl.handle.net/10138/37603.
  25. Brian S. Thomson. Real functions. Lecture Notes in Mathematics. 1170. Berlin etc.: Springer-Verlag. VII, 229 p. DM 31.50 (1985)., 1985. URL: http://dx.doi.org/10.1007/BFb0074380.
  26. Y. Wang. Randomness and Complexity. PhD dissertation, University of Heidelberg, 1996. Google Scholar
  27. K. Weihrauch. Computable Analysis. Springer, Berlin, 2000. Google Scholar
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 About DROPS Imprint Privacy Contact