December 14, 2023
Speaker: Valentino Delle Rose (Pontificia Universidad Católica de Chile and CENIA)
Title: Logical Depth of Infinite Binary Sequences and Its Relativization
Abstract: Bennett’s notion of logical depth can be seen as a way of formalizing the intuition that the same piece of information can be organized in different ways, making it more or less useful for certain purposes: in other words, such notion aims at distinguishing “useful” information from trivial one and random noise.
Roughly speaking, Bennett calls a sequence “deep” if none of its prefixes can be optimally described within any computable time bound. A natural example of deep sequence is given by the halting problem, while both Martin-Löf random and computable sequences are shallow, i.e., non-deep.
Moreover, logical depth satisfies the so-called “slow growth law”, namely deep sequences are closed upwards under tt-reductions: thus, no deep sequence can be computed “quickly” (that is, within some computable time bound) from a shallow one.
In a joint work with Laurent Bienvenu and Wolfgang Merkle, we consider a natural way of relativizing the notion of depth with the aim of better understanding how an oracle may help in organizing information. This relativization is designed to keep focusing on the same class of “fast” computations in so far, as it is defined in terms of computable time bounds and not in terms of time bounds computable in the oracle.
This relativization gains additional interest since it differs in the following respect from most other relativizations considered in computability theory. Usually, when relativizing a class, for any oracle the relativized class contains the unrelativized class or the unrelativized class contains the relativized one (and this usually follows immediately from the definition of the class in question). For the class of deep sequences the situation is different, since depth is defined in terms of the difference between time-bounded and unbounded Kolmogorov complexity: with access to an oracle, the two latter quantities stays the same or decreases but a priori the two values may decrease by different amounts, hence their difference may increase or decrease. As a consequence, a priori none of the following four cases can be ruled out for a given oracle when comparing the classes of deep sets and of sets that are deep relative to the oracle: first, the two classes may be incomparable with respect to set-theoretical inclusion, second, the unrelativized class may be strictly contained in the relativized class, third, the relativized class may be strictly contained in the unrelativized class and, fourth, the two classes may be the same. We show that the first case applies to the halting problem, while the second holds for all Martin-Löf random oracles. Moreover, we observe that every K-trivial oracle falls under the third or fourth case, while obviously case four holds for all computable oracles. It is open whether the third case holds for some or all noncomputable K-trivial oracles.
November 9, 2023
Speaker: Elvira Mayordomo (University of Zaragoza)
Title: On Normality, Supernormality, Finite State Dimension, and Point to Set Principles
Abstract: Finite state dimension is the lowest level effectivization of Hausdorff dimension and is closely related to Borel normality. In this talk I will review its main properties, prove a new characterization in terms of information content approximated at a certain precision, and consider new generalizations of normality. I will then prove a finite-state dimension point to set principle.
October 12, 2023 at Drake University
Speaker: Timothy McNicholl (Iowa State University)
Title: An Effective Gelfand Transform
Abstract: I will talk about a recent proof of an effective version of the Gelfand duality theorem for commutative unitary Banach algebras. I will presume only knowledge of basic linear algebra, analysis, and computability theory.
(Joint work with M. Harrison-Trainor, I. Goldbring, A. Melnikov, et. al.)
May 11, 2023
Speaker: Christopher Porter (Drake University)
Title: Length Functions and the Dimension of Points in Self-Similar Fractal Trees
Abstract: In this talk, I will discuss recent work on the effective dimension of points in infinite fractal trees generated recursively from a finite tree over some fixed alphabet. Using unequal costs coding, we can associate a length function with each such fractal tree and show that the channel capacity of the length function is equal to the similarity dimension of the fractal tree (up to a multiplicative constant determined by the size of the alphabet over which our tree is defined). Based on this result, one can further derive formulas for calculating the effective dimension and strong effective dimension of points in fractal trees, establishing analogues of several results due to Lutz and Mayordomo, who studied the effective dimension of points in self-similar fractals in Euclidean space. Finally, I will discuss follow-up work, conducted jointly with Adam Case, in which we apply the analogues of the Lutz/Mayordomo results to calculate the change of dimension of sequences under transformations induced by morphisms (at least for a sufficiently broad class of sequences).
April 6, 2023
March 7, 2023
Speaker: Konstantin Slutsky (Iowa State University)
Title: Partial Actions and Orbit Equivalence Relations
Abstract: In this talk, we will discuss the framework of partial actions for constructing orbit equivalent actions of Polish groups. While related ideas have been employed in ergodic theory and Borel dynamics for many years, the particular viewpoint of partial actions simplifies construction of orbit equivalent actions of distinct groups.
As an application, we will present a Borel version of Katok’s representation theorem for multidimensional Borel flows. One-dimensional flows are closely connected to actions of Z via the so-called “flow under a function” construction. This appealing geometric
picture does not generalize to higher dimensions. Within the ergodic theoretical framework, Katok introduced the concept of a special flow as a way to connect multidimensional Rd and Zd actions. We will show that similar connections continue to hold in Borel dynamics.
Another illustration of the partial actions techniques that we intend to touch is the following result: a Borel equivalence relation generated by a free R-flow can also be generated by a free action of any non-discrete and non-compact Polish group. This is in contrast with the situation for discrete groups, where amenability distinguishes groups that can and cannot generate free finite measure-preserving hyperfinite actions.
December 2, 2022
Speaker: Adam Case (Drake University)
Title: Finite-State Mutual Dimension
Abstract: In this talk, I will discuss recent work with Jack H. Lutz on a notion of finite-state mutual dimension. Intuitively, the finite-state dimension of a sequence S represents the density of finite-state information contained within S, while the finite-state mutual dimension between two sequences S and T represents the density of finite-state information shared by S and T. Thus “finite-state mutual dimension” can be viewed as a “finite-state” version of mutual dimension and as a “mutual” version of finite-state dimension. The main results that will be discussed are as follows. First, we show that finite-state mutual dimension, defined using information-lossless finite-state compressors, has all of the properties expected of a measure of mutual information. Next, we prove that finite-state mutual dimension may be characterized in terms of block mutual information rates. Finally, we provide necessary and sufficient conditions for two normal sequences to achieve finite-state mutual dimension zero.
November 11, 2022
Speaker: Linda Westrick (Pennsylvania State University)
Title: Step Functions in the Weihrauch Lattice
Abstract: For any real A in the unit interval, let sA denote the step function that jumps at A. We consider the partial order of the functions sA under Weihrauch reducibility, and start to paint the picture of how these functions are arranged. Among other results, we find a collection of left-c.e. reals indexed by σ ∈ ω<ω such that the Weihrauch reducibility of their step functions coincides with the extension relation on their indices. Joint with Arno Pauly.
October 14, 2022
Speaker: Peter Burton (Iowa State University)
Title: Permutation Replicas of Infinite Groups
Abstract: This talk will discuss the theory of using permutations of finite sets to replicate infinite discrete groups. The basic idea is to look at a large finite ‘window’ in a discrete group G and to label certain permutations of a finite set by the elements of the window. We consider these finitary permutations to be a good replica of the infinite group G if they compose as they would in the group itself, possibly with a small proportion of errors. Such objects are referred to as sofic approximations to G and a major open question in group theory is to determine whether every group G admits arbitrarily good sofic approximations, in which case G itself is said to be sofic. We will present a result due to the speaker and Lewis Bowen which constructs a group which is not sofic from the (currently unverified) hypothesis that all permutation models for groups of integers matrices come from their finite quotients. Time permitting, we will also discuss the connection between sofic approximation for groups and nonlocal games in quantum information theory.
May 5, 2022
Speaker: Anna Zamojska-Dzienio (Warsaw University of Technology and Fulbright Scholar at Iowa State University)
Title: Birkhoff-Maltsev Problem
Abstract: A quasivariety is a class of all models of some set of quasi-identities (implications of a particular form). The set Lq(K) of all subquasivarieties contained in a given quasivariety K forms a complete lattice under inclusion called a lattice of quasivarieties. In 1966 A. I. Maltsev asked the following question: Which lattices can be represented as lattices of quasivarieties?
A closely connected problem was suggested by G. Birkhoff in 1945. Since the end of nineties, this problem has become known as the Birkhoff–Maltsev problem. This is the one of the oldest and hardest open problems in lattice theory. G. Gratzer in Epilogue to the edition of his “Universal Algebra. Second Edition” from 2008 describes five main developments in universal algebra for the last 40 years from the first edition. The first one is the theory of quasivarieties and as a main driving force in the theory G. Gratzer mentions the Birkhoff–Mal’cev problem.
In this talk we present some historical positive solutions to the Birkhoff–Mal’cev problem for particular classes of lattices and then we focus on complexity of the problem. For some classical quasivarieties, the lattices of quasivarieties turned out to be “complicated” because it was difficult to find their explicit descriptions. During the half-century of studying such questions, several measures of complexity were suggested and, for a number of interesting cases, the corresponding lattices were proven to be “highly complicated”, i.e., to be of maximal possible cardinality, to satisfy no nontrivial lattice identity, to be universal in some sense. Other measures of complexity cover existence of large collections of subquasivarieties with “bad” properties e.g., without convenient axiomatisation, with undecidable natural algorithmic problems. Some results in this direction we discuss here were obtained as a joint work with Marina Schwidefsky and Anvar Nurakunov.
March 31, 2022
Speaker: Andrei Migunov (Iowa State University)
Title: Algorithmic Dimension via Learning Functions
Abstract: Many phenomena that we would like to model, and about which we need to compute, are stochastic (probabilistic) in nature. Systems governed by probability can often produce more than one path, trajectory, or output on a given input. However, there are not only random processes – there are also individual objects (say, binary sequences), which are inherently random in that they are information-dense, incompressible, and unpredictable. Dimension is a concept that refines the notion of randomness and allows us to ask how random an object (such as a binary sequence) is. Fractal dimensions and especially algorithmic fractal dimensions have applications in many areas, including medicine. They even allow computer scientists to solve long-standing open problems in mathematics that have nothing to do with computation at all. In this talk, we will connect these notions to learning functions, which make judgments and inferences from streams of data. The notion of learning we will consider is that of the Gold paradigm (E Mark Gold, 1967). A learner forms a model from a sequence of training data, and eventually must output a correct model without changing its mind later on. Zaffora Blando (2021) recently showed that learning functions can be used to characterize algorithmic randomness. We extend this work to show that learning functions can also be used to characterize the algorithmic dimension of a set of infinite binary sequences.
The results that will be discussed in this talk are a joint work with Jack H. Lutz.
February 24, 2022
Speaker: James Freitag (University of Illinois Chicago)
Title: Model Theory and Learning Theory
Abstract: Model theory is a part of mathematical logic, where the central goal is to study definable sets in first order structures. In general, this task is impossible because of logical phenomena like undecidability. Instead the central approach of modern model theory is to work with some combinatorial tameness assumption which makes the development of a structure theory for definable sets possible. As it turns out, it is now known that several of these tameness assumptions are precisely the dividing lines between learnability and non-learnability under various models (e.g. PAC, online, and learning). In this talk, we will describe some of these connections, as well as how both subjects have benefitted from this connection.
December 17, 2021
Speaker: Laurent Bienvenu (CNRS & Université de Bordeaux)
Title: New Results on Logical Depth
Abstract: In algorithmic information theory, complexity is equated with randomness, therefore we find ourselves in a seemingly paradoxical situation where a higher complexity value is assigned to a random string of symbols than, say, Tolstoy’s novel War and Peace. Bennett’s notion of logical depth is an attempt to resolve this paradox. We will review this notion and discuss some of its important properties. We will also present several recent results that support the intuition that no (reasonable) random process can be used to generate a deep object. This is joint work with Chris Porter.
November 19, 2021
Speaker: Chris Porter (Drake University)
Title: Continuous Randomness via Transformations of 2-Random Sequences
Abstract: Reimann and Slaman initiated the study of sequences that are Martin-Löf random with respect to a continuous measure, establishing fundamental facts about NCR, the collection of sequences that are not Martin-Löf random with respect to any continuous measure. In the case of sequences that are Martin-Löf random with respect to a computable, continuous measure, the picture is fairly well-understood: such sequences are truth-table equivalent to a Martin-Löf random sequence. However, given a sequence that is Martin-Löf random with respect to a continuous measure but not with respect to any computable measure, we can ask: how effective is the measure with respect to which it is continuously random? In this talk, I will present initial work on this question, discussing several results on sequences that are continuously random with respect to a measure that is computable in 0’.
October 12, 2021
Speaker: Caleb Camrud (Iowa State University)
Title: Computable Infinitary Continuous Logic
May 3, 2021
Speaker: Andrew Marks (UCLA)
Title: Descriptive Set Theory and Geometrical Paradoxes
Abstract: In 1925 Tarski posed the problem of whether a disc in the plane can be partitioned into finitely many pieces which can be rearranged by isometries to form a square of the same area. This problem was solved in the affirmative in 1990 by Laczkovich, but the solution was non-constructive and used the axiom of choice. In this talk we will discuss a completely constructive solution to the problem, joint with Spencer Unger, and describe an explicit Borel way to equidecompose a circle and a square.
A key ingredient in the proof is recent progress in a research program in descriptive set theory to understand how the complexity of a countable group is related to the complexity of its Borel actions. We will also discuss some new results in this area joint with Clinton Conley, Steve Jackson, Brandon Seward, and Robin Tucker-Drob.
March 31, 2021
Speaker: Satuadev Nandakumar (Indian Institute of Technology Kanpur)
Title: Algorithmic Randomness and Continued Fractions
Abstract: We present our recent works initiating the connections between algorithmic randomness and the continued fraction expansion of reals in the unit interval.
It is desirable that randomness is an intrinsic property of a number, rather than an artifact of a particular representation of the number. This is not always true – for example, there are base-2 normals which are not base-3 normal. But for sufficiently general notions of randomness like Martin-Löf randomness and computable randomness, we expect the randomness of a number to be independent of its representation.
Towards the above ideal, we define a notion of Martin-Löf and computable randomness for continued fractions, and show that a real has a Martin-Löf (or computable) random binary expansion if and only if its continued fraction is Martin-Löf (respectively, computably) random.
To study the notion of the rate of information, we introduce a notion of Hausdorff dimension, and demonstrate the construction of dimension 1 and dimension 0 continued fractions. In the latter construction, we introduce a variant of the dilution method which sheds insight on the interaction between randomness and alphabet size.
Further, we introduce the basic framework for connecting this approach to the well-known theory of continued fraction normals. One of the first steps is to establish that “disjoint block frequency” and “sliding block frequency” are equal for continued fraction normals. We prove this using an analogue of Pillai’s theorem for base-10 expansions. We illustrate the utility of this theorem by giving a combinatorial proof of Heersink and Vandehey’s result that for any continued fraction normal, every subsequence chosen according to a non-trivial arithmetic progression yields a non-normal, in sharp contrast with binary normality.
December 11, 2020
Speaker: Adam Case (Drake University)
Title: Some Results on Mutual Dimension and Independence
Abstract: Recent work in effective dimension has resulted in the development of a new framework, called mutual dimension, for quantifying the density of shared algorithmic information between two sequences. In this talk, I will discuss some of the known relationships between mutual dimension and independently random sequences. I will also present new preliminary results that provide insights into how these concepts and relationships may be adapted to a finite-state setting. The research presented in this talk is a joint work with Jack H. Lutz.
October 30, 2020
Speaker: Damir Dzhafarov (University of Connecticut)
Title: Reduction Games, Provability, and Compactness
Abstract: Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between given Pi12 principles over omega-models of RCA0. They also introduced a version of this game that similarly captures provability over (full) RCA0. We generalize this game for provability over arbitrary subsystems of second-order arithmetic, and establish a compactness argument that shows that certain winning strategies can always be chosen to win in a number of moves bounded by a number independent of the instance of the principles being considered. Our compactness result also generalizes an old proof-theoretic fact due to H. Wang, and has a number of other applications. This is joint work with Denis Hirschfeldt and Sarah Reitzes.
April 9, 2020
Speaker: Donald Stull (Iowa State University)
Title: Effective Dimension and Projections
Abstract: Effective dimensions, introduced by Jack Lutz in the early 2000s, use computability theory to quantify the fine-grained randomness of individual points in Euclidean space. Recent results have shown that algorithmic information techniques can answer questions in geometric measure theory. In this talk, we discuss recent and ongoing work on this topic. In particular, we will focus on the application of effective dimension to projection problems. Determining the (classical) fractal dimensions of a set projected onto a subspace is a central theme of geometric measure theory. We will show that algorithmic techniques can shed light on these questions, as well as discuss directions for future research.
March 5, 2020 at Drake University
Speaker: Timothy McNicholl (Iowa State University)
Title: An Application of Computable Probability Theory to Computable Analysis
Abstract: We consider the question as to whether the exponent of a computably presentable Lebesgue space whose dimension is at least 2 must be computable. We show this very natural conjecture is true when the exponent is at least 2 or when the space is finite-dimensional. However, we also show there is no uniform solution even when given upper and lower bounds on the exponent. The proof of this result leads to some basic results on the effective theory of stable random variables.
December 5, 2019 at Drake University
Speaker: Mark Johnson (Central College)
Title: A Visit from a Ghost of Set Theory Past
Abstract: Given an uncountable set X in a forcing extension, what can be said about infinite subsets of X in the ground model? We explore this question for common partial orders that add reals, as well as their iterations. This work is originally from my dissertation, so I will also tell some of the story of why I’m returning to it now.
November 7, 2019 at Iowa State University
Speaker: Chris Porter (Drake University)
Title: New Developments on Algorithmically Random Closed Sets
Abstract: In this talk, I will discuss recent joint work with Adam Case on algorithmically random closed subsets of Cantor space. In earlier work, Cenzer and Weber studied the behavior of various biased random closed sets under unions and intersections, showing that these operations preserve randomness in the sense that performing such an operation on a pair of relatively random closed sets results in a closed set that is random with respect to the measure induced by the operation. We obtain partial converses of these results, answering the following question: Given a closed set that is random with respect to a certain biased measure, when can it be obtained as the union or intersection of a pair of relatively random closed sets (that are random with respect to an appropriately chosen measure)? In addition, I will discuss some results on multiple intersections of random closed sets that have emerged from this work.
October 3, 2019 at Grinnell College
Speaker: Neil Lutz (Iowa State University)
Title: Algorithmic Dimensions of Projected Points
Abstract: To what extent are fractal dimensions preserved by projection mappings? In this talk, we will consider an effective and pointwise version of this question in the Euclidean plane. I will describe recent progress on this question and show how it has yielded new results about the classical Hausdorff dimension of projected sets, including new extensions to Marstrand’s projection theorem.
April 25, 2019 at Grinnell College
Speaker: Diego Rojas (Iowa State University)
Title: A Framework for the Reverse Mathematics of Free Quasigroups
Abstract: The notion of a group generalizes to a quasigroup, a set equipped with a binary operation * in which knowledge of any two arguments in an equation of the form a*b=c determines the third one uniquely. In this talk, we discuss a framework for studying theorems about quasigroup words in the setting of reverse mathematics. In particular, we show that Evans’ Normal Form Theorem for quasigroup words is provable in RCA0 using this framework, and we mention some future work in this direction. This is joint work with Alex Nowak.
March 28, 2019 at Drake University
Speaker: Titus Klinge (Carleton College)
Title: Real-Time Equivalence of Chemical Reaction Networks and Analog Computers
March 12, 2019 at Iowa State University
Speaker: Xiang Huang (Iowa State University)
Title: Asymptotic Divergences and String Dichotomy
Abstract: The Schnorr-Stimm dichotomy theorem concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet. The theorem asserts that, for any such sequence S, the following two things are true.
- If S is not normal, then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on S.
- If S is normal, then any finite-state gambler betting on S loses money at an exponential rate betting on S.
In this paper, we use the Kullback-Leibler divergence to formulate asymptotic divergences and to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem. Some connections to finite state dimension are also discussed.
December 6, 2018 at Iowa State University
Speaker: Adam Case (Drake University)
Title: Automata, Compression, and Dimension
Abstract: One of the first topics discussed in an undergraduate theory of computation course is finite-state automata. This model of computation is often viewed as an “acceptor,” that is, a machine that either accepts or rejects its input strings. In this talk we examine finite-state compressors (FSCs), a modification of finite-state automata that reads an input string and produces an output string. We discuss the compression properties of FSCs that are information-lossless and compare them to the well-known LZ78 compression algorithm. Compressors based on other kinds of automata will also be explored, along with various relationships between compression and dimension.
November 1, 2018 at Grinnell College
Speaker: Timothy McNicholl (Iowa State University)
Title: Effective Metric Structure Theory
Abstract: We will survey recent work on extending the classical computable structure theory program to uncountable metric structures by means of the framework of computable analysis. Specifically, we will summarize results on degrees of categoricity, index sets, and computable presentability for metric spaces and Banach space, especially Lebesgue spaces.
October 4, 2018 at Drake University
Speaker: Jack Lutz (Iowa State University)
Title: Algorithmic Randomness in Chemical Reaction Networks: Logic meets Nanotechnology
Abstract: This talk is an introduction to the following three things.
Chemical reaction networks. These are mathematical objects that serve simultaneously in three different roles.
- They are models of chemical processes in well-mixed solutions.
- They form a general-purpose programming language in the ordinary sense.
- They form a programming language for nanotechnology.
Algorithmic randomness. This is a theory of what it means for an individual stream of data to be random. It is a beautiful theory that had to wait for computer science to be formulated coherently.
April 26, 2018 at Grinnell College
Speaker: Tyler Brown (Iowa State University)
Title: Analytic Computable Structure Theory and Non-Purely Atomic Lp Spaces
Abstract: Suppose that p ≥ 1 is a computable real. In this talk, we extend previous work of Clanin, Stull, and McNicholl by classifying the computable Lp spaces whose underlying measure spaces are atomic but not purely atomic. We will also discuss the methods used to determine the degrees of categoricity of these spaces, analyzing the complexity of associated projection maps along the way.
April 5, 2018 at Iowa State University
Speaker: Chris Porter
Title: Negligibility, Depth, and Algorithmic Randomness
Abstract: In this talk I will discuss joint work with Laurent Bienvenu on deep PI 0 1 classes, which are highly structured effectively closed classes with the property that it is difficult to compute initial segments of their members with high probability. Connections to algorithmic randomness will also be discussed.
February 22, 2018 at Drake University
Speaker: Peter Dixon (Iowa State University)
Title: Time Vs Space and Connections to Derandomization
Abstract: A classical result of Hopcroft, Paul and Valiant shows that every Turing machine that runs in time O(t) can be simulated using O(t/log t) space. We discuss about extending this result to randomized computations and an application to derandomization of probabilistic time-bounded computations.
No background on complexity theory is assumed for the talk.
November 9, 2017 at Iowa State University
Speaker: Johanna Franklin (Hofstra University)
Title: Computable Categoricity of Random Fields
Abstract: The algebraic fields of characteristic 0 can be classified using a computable homeomorphism onto Cantor space. This enables us to define a random field as one that is mapped to a random element of Cantor space. In this
talk, I will discuss the computable categoricity of random fields in the contexts of two different languages: the standard language of fields and an expanded language with root predicates that hold when their inputs define polynomials that have roots in the field under consideration.
This work is joint with Russell Miller.
October 12, 2017 at Drake University
Speaker: Joseph Mileti (Grinnell College)
Title: Randomness and Reverse Mathematics
Abstract: In logic, Reverse Mathematics provides a framework to measure the inherent complexity of any proof of a given theorem. The vast majority of the theorems that logicians initially analyzed fell into a small handful of complexity classes. However, in recent years, we have discovered many theorems that do not fit into this clean picture. In this talk, we will give an overview on the area, and focus on results where randomness plays a key role.
September 14, 2017 at Grinnell College
Speaker: Donald Stull (Iowa State University)
Title: Effective Dimension of Points and Lines
Abstract: This talk will cover recent work using Kolmogorov complexity to study the dimension of points on lines in the Euclidean plane and its application to important questions in fractal geometry. In particular, we will show that this work strengthens the lower bounds of the dimension of Furstenberg sets. We will also discuss future research and open problems in this area.
April 20, 2017 at Drake University
Speaker: Adam Case (Drake University)
Title: Turing Reductions and Data Processing Inequalities for Sequences
Abstract: A data processing inequality states that the quantity of shared information between two entities (e.g. signals, strings) cannot be significantly increased when one of the entities is processed by certain kinds of transformations. We prove the existence of several data processing inequalities for sequences, where the transformations are bounded Turing functionals and the quantity of shared information is measured by the lower and upper mutual dimensions between sequences.
Specifically, we show that, for all sequences X, Y, and Z, if Z is computable Lipschitz reducible to X, then
mdim(Z : Y ) ≤ mdim(X : Y ) and Mdim(Z : Y ) ≤ Mdim(X : Y ).
We also show how to derive other data processing inequalities by making adjustments to the computable bounds of the use and yield of a Turing functional.
March 23, 2017 at Iowa State University
Speaker: Titus Klinge (Grinnell College)
February 16, 2017 at Grinnell College
Speaker: Timothy McNicholl (Iowa State University)
December 1, 2016 at Iowa State University
Speaker: Chris Porter (Drake University)
Title: Kolmogorov Complexity and Generalized Length Functions
Abstract: Kolmogorov complexity measures the algorithmic complexity of a finite binary string σ in terms of the length of the shortest description σ∗ of σ. Traditionally, the length of σ∗ is taken to measure the amount of information contained in σ. However, we may also view the length of σ∗ as a measure of the cost of producing σ, which permits one to generalize the notion of length, wherein the cost of producing a 0 or a 1 can vary in some prescribed manner. In this talk, I will discuss this generalization of length based on the above information cost interpretation and a modification of the definition of Kolmogorov complexity in terms of generalized length functions. I will focus on a specific class of generalized length functions (called k-length functions) that are intimately related to a subcollection of the Bernoulli p-measures, namely those corresponding to the unique computable real p ∈ (0, 1) such that pk = 1 − p for k ≥ 1. Lastly, I will present a generalization of the classic Levin-Schnorr theorem that involves k-length functions and subsequent results that involve effective dimension and entropy. This is joint work with Cameron Fraize.
November 3, 2016 at Drake University
Speaker: Pavan Aduri (Iowa State University)
Title: Kolmogorov Complexity and Computational Complexity
Abstract: Kolmogorov complexity concerns with the amount of information present in individual objects. Computational complexity attempts to understand the amount of resources needed to solve computational problems in various computational models. In this talk we will give a overview about the connections between Kolmogorov complexity and computational complexity. We will explore the role of Kolmogorov complexity in randomness extractors, communication complexity and characterization of complexity classes. We will survey a few known results and highlight some open questions. No background in Kolmogorov complexity or computation complexity is assumed. Part of the talk is based on joint works with John Hitchcock and N. V. Vinodchandran
October 6, 2016 at Grinnell College
Speaker: Jack Lutz (Iowa State University)
Title: Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension
Abstract: Theoretical computer scientists are sometimes accused of insufficient attention to applications. In that spirit, this talk is devoted to an application of the theory of computing. The application is to pure mathematics!
We formulate the conditional Kolmogorov complexity of x given y at precision r, where x and y are points in Euclidean spaces and r is a natural number. We demonstrate the utility of this notion in two ways.
1. We prove a point-to-set principle that enables one to use the (relativized, constructive) dimension of a single point in a set E in a Euclidean space to establish a lower bound on the (classical) Hausdorff dimension of E. We then use this principle, together with conditional Kolmogorov complexity in Euclidean spaces, to give a new proof of the known, two-dimensional case of the Kakeya conjecture. This theorem of geometric measure theory, proved by Davies in 1971, says that every plane set containing a unit line segment in every direction has Hausdorff dimension 2.
2. We use conditional Kolmogorov complexity in Euclidean spaces to develop the lower and upper conditional dimensions dim(x|y) and Dim(x|y) of x given y, where x and y are points in Euclidean spaces. Intuitively these are the lower and upper asymptotic algorithmic information densities of x conditioned on the information in y. We prove that these conditional dimensions are robust and that they have the correct information-theoretic relationships with the well-studied dimensions dim(x) and Dim(x) and mutual dimensions mdim(x:y) and Mdim(x:y).
This is joint work with Neil Lutz.