Full Record

Author | Lutz, Neil J. |

Title | Algorithmic information, fractal geometry, and distributed dynamics |

URL | https://rucore.libraries.rutgers.edu/rutgers-lib/55576/ |

Publication Date | 2017 |

Degree | PhD |

Discipline/Department | Computer Science |

Degree Level | doctoral |

University/Publisher | Rutgers University |

Abstract | This 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. |

Subjects/Keywords | Kolmogorov complexity |

Contributors | Wright, Rebecca N (chair); Allender, Eric (internal member); Saraf, Shubhangi (internal member); Braverman, Mark (outside member); School of Graduate Studies |

Language | en |

Rights | The author owns the copyright to this work. |

Country of Publication | us |

Format | 1 online resource (vi, 122 p. : ill.) |

Record ID | oai:example.org:rutgers-lib:55576 |

Other Identifiers | rutgers-lib:55576; ETD_8228 |

Repository | rutgers |

Date Indexed | 2019-08-21 |

Sample Images | Cited Works

- [1] Ittai Abraham, Danny Dolev, Rica Gonen, and Joe Halpern. Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In Proceedings of the 25th annual ACM Symposium on Principles of Distributed Computing (PODC ’06), pages 53–62, New York, NY, 2006. ACM.
- [2] Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo. Effective strong dimension in algorithmic information and computational complexity. SIAM J. Comput., 37(3):671–705, 2007.
- [3] Yakov Babichenko. Uncoupled automata and pure Nash equilibria. Int. J. Game Theory, 39(3):483–502, 2010.
- [4] Yakov Babichenko. Completely uncoupled dynamics and Nash equilibria. Games and Economic Behavior, 76(1):1–14, 2012.
- [5] Yakov Babichenko, Yuval Peres, Ron Peretz, Perla Sousi, and Peter Winkler. Hunter, Cauchy rabbit, and optimal Kakeya sets. Trans. Amer. Math. Soc., 366:5567–5586, 2014).
- [6] Maria-Florina Balcan, Florin Constantin, and Ruta Mehta. The weighted majority algorithm does not converge in nearly zero-sum games. ICML Workshop on Markets, Mechanisms and Multi-Agent Models, 2012.
- [7] Michael Ben-Or. Randomized agreement protocols. In Fault-Tolerant Distributed Computing, pages 72–83, 1986.
- [8] A. S. Besicovitch. Sur deux questions d’intégrabilité des fonctions. Journal de la Société de physique et de mathematique de l’Universite de Perm, 2:105–123, 1919.
- [9] A. S. Besicovitch. On Kakeya’s problem and a similar one. Mathematische Zeitschrift, 27:312–320, 1928.
- [10] P. Billingsley. Hausdorff dimension in probability theory II. Illinois Journal of Mathematics, 5(2):291–298, 1961.
- [11] Christopher J. Bishop. Personal communication, April 27, 2017.
- [12] Christopher J. Bishop and Yuval Peres. Fractals in Probability and Analysis. Cambridge University Press, 2017.
- [13] Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In Proceedings of the 25th annual ACM Symposium on Theory of Computing (STOC ’93), pages 91–100, 1993. 117
- [14] James E. Burns. Self-stabilizing rings without demons. Technical Report GIT-ICS87/36, School of Information and Computer Science, Georgia Institute of Technology, November 1987.
- [15] Adam Case and Jack H. Lutz. Mutual dimension. ACM Transactions on Computation Theory, 7(3):12, 2015.
- [16] Adam Case and Jack H. Lutz. Mutual dimension and random sequences. In Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, pages 199–210, 2015.
- [17] Gregory J. Chaitin. On the length of programs for computing finite binary sequences. J. ACM, 13(4):547–569, 1966.
- [18] Gregory J. Chaitin. On the length of programs for computing finite binary sequences: statistical considerations. J. ACM, 16(1):145–159, 1969.
- [19] Thomas R. Cover and Joy A. Thomas. Elements of Information Theory. Wiley, second edition, 2006.
- [20] Colleen D. Cutler. Strong and weak duality principles for fractal dimension in Euclidean space. Math. Proc. Camb. Phil. Soc., 118:393–410, 1995.
- [21] Constantinos Daskalakis, Rafael Frongillo, Christos H. Papadimitriou, George Pierrakos, and Gregory Valiant. On learning algorithms for Nash equilibria. In Spyros Kontogiannis, Elias Koutsoupias, and Paul G. Spirakis, editors, Algorithmic Game Theory: Third International Symposium, SAGT 2010, Athens, Greece, October 18– 20, 2010. Proceedings, pages 114–125. Springer Berlin Heidelberg, 2010.
- [22] Roy O. Davies. Some remarks on the Kakeya problem. Proc. Cambridge Phil. Soc., 69:417–421, 1971.
- [23] Edsger W. Dijkstra. Self-stabilizing systems in spite of distributed control. Commun. ACM, 17(11):643–644, 1974.
- [24] Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. On the minimal synchronism needed for distributed consensus. J. ACM, 34(1):77–97, 1987.
- [25] Danny Dolev, Michael Erdmann, Neil Lutz, Michael Schapira, and Adva Zair. Brief announcement: Stateless computation. In Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC 2017), to appear.
- [26] Shlomi Dolev. Self-Stabilization. MIT Press, 2000.
- [27] Randall Dougherty, Jack H. Lutz, R. Daniel Mauldin, and Jason Teutsch. Translating the Cantor set by a random real. Transactions of the American Mathematical Society, 366:3027–3041, 2014.
- [28] Rod Downey and Denis Hirschfeldt. Springer-Verlag, 2010. Algorithmic Randomness and Complexity.
- [29] Zeev Dvir. On the size of Kakeya sets in finite fields. J. Amer. Math. Soc., 22:1093– 1097, 2009. 118
- [30] K. J. Falconer. Fractal Geometry: Mathematical Foundations and Applications. Wiley, 1990.
- [31] K. J. Falconer. Techniques in Fractal Geometry. Wiley, 1997.
- [32] Kenneth Falconer. Fractal Geometry: Mathematical Foundations and Applications. Wiley, third edition, 2014.
- [33] Kenneth J. Falconer. The Geometry of Fractal Sets. Cambridge University Press, 1985.
- [34] Kenneth J. Falconer. Sets with large intersection properties. Journal of the London Mathematical Society, 49(2):267–280, 1994.
- [35] Faith Fich and Eric Ruppert. Hundreds of impossibility results for distributed computing. Distributed Computing, 16(2–3):121–163, 2003.
- [36] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374–382, 1985.
- [37] O. Frostman. Potential d’equilibre et capacité des ensembles avec quelques applications à la theórie des fonctions. Meddel. Lunds Univ. Math. Sen., 3:1–118, 1935.
- [38] Timothy G. Griffin, F. Bruce Shepherd, and Gordon Wilfong. The stable paths problem and interdomain routing. IEEE/ACM Trans. Netw., 10(2):232–243, 2002.
- [39] Xiaoyang Gu and Jack H. Lutz. Dimension characterizations of complexity classes. Computational Complexity, 17(4):459–474, 2008.
- [40] Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo. Points on computable curves. In FOCS, pages 469–474, 2006.
- [41] Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, and Philippe Moser. Dimension spectra of random subfractals of self-similar fractals. Ann. Pure Appl. Logic, 165(11):1707– 1726, 2014.
- [42] Joseph Y. Halpern and Yoram Moses. Knowledge and common knowledge in a distributed environment. J. ACM, 37(3):549–587, July 1990.
- [43] Sergiu Hart. Adaptive heuristics. Econometrica, 73(5):1401–1430, 2005.
- [44] Sergiu Hart and Yishay Mansour. How long to equilibrium? The communication complexity of uncoupled equilibrium procedures. Games and Economic Behavior, 69(1):107–126, 2010.
- [45] Sergiu Hart and Andreu Mas-Colell. Uncoupled dynamics do not lead to Nash equilibrium. American Economic Review, 93(5):1830–1836, 2003.
- [46] Sergiu Hart and Andreu Mas-Colell. Stochastic uncoupled dynamics and Nash equilibrium. Games and Economic Behavior, 57(2):286–303, 2006.
- [47] Sergiu Hart and Andreu Mas-Colell. Simple Adaptive Strategies: From Regretmatching to Uncoupled Dynamics. World Scientific Publishing Co., Inc., River Edge, NJ, 2012. 119
- [48] Felix Hausdorff. Dimension und äusseres Mass. Mathematische Annalen, 79:157–179, 1919.
- [49] Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. J. ACM, 46(6):858–923, 1999.
- [50] Michael Hochman. Lectures on dynamics, fractal geometry, and metric number theory. Journal of Modern Dynamics, 8(3–4):437–497, 2014.
- [51] Aaron D. Jaggard, Neil Lutz, Michael Schapira, and Rebecca N. Wright. Selfstabilizing uncoupled dynamics. In Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT ’14), pages 74–85, 2014.
- [52] Aaron D. Jaggard, Neil Lutz, Michael Schapira, and Rebecca N. Wright. Dynamics at the boundary of game theory and distributed computing. ACM Transactions on Economics and Computation, to appear.
- [53] Aaron D. Jaggard, Michael Schapira, and Rebecca N. Wright. Distributed computing with adaptive heuristics. In Proceedings of the Second Symposium on Innovations in Computer Science (ICS 2011), pages 417–443, 2011.
- [54] Jean-Pierre Kahane. Sur la dimension des intersections. In Jorge Alberto Barroso, editor, Aspects of mathematics and its applications, North-Holland Mathematical Library, 34, pages 419–430. Elsevier, 1986.
- [55] Nets Hawk Katz and Terence Tao. Some connections between Falconers distance set conjecture and sets of Furstenburg type. New York J. Math, 7:149–187, 2001.
- [56] Robert D. Kleinberg, Katrina Ligett, Georgios Piliouras, and Éva Tardos. Beyond the Nash equilibrium barrier. In Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 7–9, 2011. Proceedings, pages 125–140, 2011.
- [57] Andrei N. Kolmogorov. On the Shannon theory of information transmission in the case of continuous signals. IRE Transactions on Information Theory, 2(4):102–108, 1956.
- [58] Elias Koutsoupias and Christos H. Papadimitriou. Worst-case equilibria. In STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4–6, 1999, Proceedings, pages 404–413, 1999.
- [59] Roger Lagunoff and Akihiko Matsui. Asynchronous choice in repeated coordination games. Econometrica, 65(6):1467–1477, 1997.
- [60] Leonid A. Levin. On the notion of a random sequence. Soviet Math Dokl., 14(5):1413– 1416, 1973.
- [61] Leonid A. Levin. Laws of information conservation (nongrowth) and aspects of the foundation of probability theory. Problemy Peredachi Informatsii, 10(3):30–35, 1974.
- [62] Ming Li and Paul M.B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, third edition, 2008.
- [63] Jack H. Lutz. Dimension in complexity classes. SIAM J. Comput., 32(5):1236–1259, 2003. 120
- [64] Jack H. Lutz. The dimensions of individual strings and sequences. Inf. Comput., 187(1):49–79, 2003.
- [65] Jack H. Lutz and Neil Lutz. Lines missing every random point. Computability, 4(2):85–102, 2015.
- [66] Jack H. Lutz and Neil Lutz. Algorithmic information, plane kakeya sets, and conditional dimension. In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8–11, 2017, Hannover, Germany, pages 53:1–53:13, 2017.
- [67] Jack H. Lutz and Elvira Mayordomo. Dimensions of points in self-similar fractals. SIAM Journal of Computing, 38(3):1080–1112, 2008.
- [68] Jack H. Lutz and Klaus Weihrauch. Connectivity properties of dimension level sets. Mathematical Logic Quarterly, 54:483–491, 2008.
- [69] Neil Lutz. Fractal intersections and products via algorithmic dimension, 2016.
- [70] Neil Lutz and D. M. Stull. Bounding the dimension of points on a line. In TV Gopal, Gerhard Jaeger, and Silvia Steila, editors, Theory and Applications of Models of Computation: 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings, pages 425–439, 2017.
- [71] Neil Lutz and D. M. Stull. Dimension spectra of lines. In Computability in Europe 2017: Unveiling Dynamics and Complexity (CiE 2017), to appear.
- [72] Nancy Lynch. A hundred impossibility proofs for distributed computing. In Proceedings of the Eighth annual ACM Symposium on Principles of Distributed Computing (PODC ’89), pages 1–28, 1989.
- [73] Jason R Marden and Jeff S Shamma. Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation. Games and Economic Behavior, 75(2):788–808, 2012.
- [74] John M. Marstrand. Some fundamental geometrical properties of plane sets of fractional dimensions. Proceedings of the London Mathematical Society, 4(3):257–302, 1954.
- [75] Per Martin-Löf. The definition of random sequences. 9(6):602–619, 1966. Information and Control,
- [76] Pertti Mattila. Hausdorff dimension and capacities of intersections of sets in n-space. Acta Mathematica, 152:77–105, 1984.
- [77] Pertti Mattila. On the Hausdorff dimension and capacities of intersections. Mathematika, 32:213–217, 1985.
- [78] Pertti Mattila. Geometry of sets and measures in Euclidean spaces: fractals and rectifiability. Cambridge University Press, 1995.
- [79] Elvira Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorff dimension. Inf. Process. Lett., 84(1):1–3, 2002. 121
- [80] Joseph S. Miller. “Open Questions” section of personal webpage. Retrieved October 30, 2016. https://web.archive.org/web/20161021183028/http://www.math. wisc.edu/~jmiller/open.html.
- [81] Ursula Molter and Ezequiel Rela. Furstenberg sets for a fractal set of directions. Proc. Amer. Math. Soc., 140:2753–2765, 2012.
- [82] Dov Monderer and Lloyd S. Shapley. Potential games. Games and Economic Behavior, 14:124–143, 1996.
- [83] Andre Nies. Computability and Randomness. Oxford University Press, Inc., New York, NY, USA, 2009.
- [84] Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1–2):166–196, 2001.
- [85] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, New York, NY, 2007.
- [86] Tuomas Orponen. An improved bound on the packing dimension of Furstenberg sets in the plane, 2016.
- [87] Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci., 48(3):498–532, 1994.
- [88] Christos H. Papadimitriou and Georgios Piliouras. From Nash equilibria to chain recurrent sets: Solution concepts and topology. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14–16, 2016, pages 227–235, 2016.
- [89] Yakov Pesin. Dimension Theory in Dynamical Systems: Contemporary Views and Applications. University of Chicago Press, 1998.
- [90] Bary S. R. Pradelski and H. Peyton Young. Learning efficient Nash equilibria in distributed systems. Games and Economic Behavior, 75(2):882–897, 2012.
- [91] Jan Reimann. Effective multifractal spectra. http://www.personal.psu.edu/ jsr25/Lectures/CFTM_2014_talk_Reimann.pdf. Lecture slides.
- [92] Jan Reimann. Computability and fractal dimension. PhD thesis, Heidelberg University, 2004.
- [93] Ezequiel Rela. Refined size estimates for Furstenberg sets via Hausdorff measures: a survey of some recent results. In M. Cepedello Boiso, H. Hedenmalm, M.A. Kaashoek, A. Montes Rodrguez, and S. Treil, editors, Concrete Operators, Spectral Theory, Operators in Harmonic Analysis and Approximation, pages 421–454. Springer, 2014.
- [94] Robert W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory, 2:65–67, 1973. 10.1007/BF01737559.
- [95] Michael E. Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput., 29(5):1449–1483, 2000. 122
- [96] Claude E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27(3–4):379–423, 623–656, 1948.
- [97] Alexander Shen and Nikolai K. Vereshchagin. Logical operations and Kolmogorov complexity. Theoretical Computer Science, 271(1–2):125–129, 2002.
- [98] Pablo Shmerkin. On Furstenberg’s intersection conjecture, self-similar measures, and the lq norms of convolutions, 2016.
- [99] Ray J. Solomonoff. A formal theory of inductive inference. Information and Control, 7(1-2):1–22, 224–254, 1964.
- [100] Elias M. Stein and Rami Shakarchi. Real Analysis: Measure Theory, Integration, and Hilbert Spaces. Princeton Lectures in Analysis. Princeton University Press, 2005.
- [101] Dennis Sullivan. Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups. Acta Mathematica, 153(1):259–277, 1984.
- [102] Terence Tao. From rotating needles to stability of waves: emerging connections between combinatorics, analysis, and PDE. Notices Amer. Math. Soc, 48:294–303, 2000.
- [103] Claude Tricot. Two definitions of fractional dimension. Mathematical Proceedings of the Cambridge Philosophical Society, 91(1):57–74, 1982.
- [104] Daniel Turetsky. Connectedness properties of dimension level sets. Theoretical Computer Science, 412(29):3598–3603, 2011.
- [105] Alan M. Turing. On computable numbers, with an application to the Entscheidungsproblem. A correction. Proceedings of the London Mathematical Society, 43(2):544–546, 1937.
- [106] Klaus Weihrauch. Computable Analysis: An Introduction. Springer, 2000.
- [107] T. Wolff. Recent work connected with the Kakeya problem. Prospects in Mathematics, pages 129–162, 1999.
- [108] Meng Wu. A proof of Furstenberg’s conjecture on the intersections of ×p and ×qinvariant sets, 2016.
- [109] Kiho Yoon. The effective minimax value of asynchronously repeated games. Int. J. Game Theory, 32(4):431–442, 2004.
- [110] H. Peyton Young. Learning by trial and error. Games and Economic Behavior, 65(2):626–643, 2009.
- [111] Lai-Sang Young. Dimension, entropy and Lyapunov exponents. Ergodic Theory and Dynamical Systems, 2:109–124, 1982.
- [112] Andriy Zapechelnyuk. Better-reply dynamics with bounded recall. Math. Oper. Res., 33(4):869–879, 2008.