Home
Resource
Algorithmic information, fractal geometry, and distributed dynamics
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(680.19 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Lutz, Neil J.. Algorithmic information, fractal geometry, and distributed dynamics. Retrieved from https://doi.org/doi:10.7282/T3639SV4

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleAlgorithmic information, fractal geometry, and distributed dynamics
NameLutz, Neil J. (author); Wright, Rebecca N (chair); Allender, Eric (internal member); Saraf, Shubhangi (internal member); Braverman, Mark (outside member); Rutgers University; School of Graduate Studies
Date Created2017
Other Date2017-10 (degree)
SubjectComputer Science, Kolmogorov complexity
Extent1 online resource (vi, 122 p. : ill.)
DescriptionThis dissertation applies two distinct algorithmic perspectives to questions in the field of fractal geometry and dynamics. In Part I, we establish connections between algorithmic information theory and classical fractal geometry. Working in Euclidean spaces, we characterize Hausdorff and packing dimensions in terms of relativized Kolmogorov complexity, and we develop conditional dimensions. These tools give rise to new dimensional bounding techniques, which we apply to problems in fractal geometry. Most significantly, we prove that a classical dimension bound for intersections of Borel sets holds for arbitrary sets, and we give a new lower bound on the Hausdorff dimension of generalized Furstenberg sets. In Part II, we use ideas from distributed computing and game theory to study dynamic and decentralized environments in which computational nodes interact strategically and with limited information. We exhibit a general non-convergence result for a broad class of dynamics in asynchronous settings. For uncoupled game dynamics, in which preferences are private inputs, we give new bounds on the recall necessary for self stabilization to an equilibrium.
NotePh.D.
NoteIncludes bibliographical references
Noteby Neil J. Lutz
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3639SV4
Languageeng
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024