Hunter R. Johnson
Research Subjects
Research Interests
Hunter R. Johnson has a total of 1 co-authors. Here are the top co-authors by number of shared publications:
M. C. Laskowski
University of Maryland
1 shared publication
Latest Publications
- Open Access
Binary strings of finite VC dimension
Any binary string can be associated with a unary predicate $P$ on $\mathbb{N}$. In this paper we investigate subsets named by a predicate $P$ such that the relation $P(x+y)$ has finite VC dimension. This provides a measure of complexity for binary strings with different properties than the standard string complexity function (based on diversity of substrings). We prove that strings of bounded VC dimension are meagre in the topology of the reals, provide simple rules for bounding the VC dimension of a string, and show that the bi-infinite strings of VC dimension $d$ are a non-sofic shift space. Additionally we characterize the irreducible strings of low VC dimension (0,1 and 2), and provide connections to mathematical logic.Open AccessBinary strings of finite VC dimension
Any binary string can be associated with a unary predicate $P$ on $\mathbb{N}$. In this paper we investigate subsets named by a predicate $P$ such that the relation $P(x+y)$ has finite VC dimension. This provides a measure of complexity for binary strings with different properties than the standard string complexity function (based on diversity of substrings). We prove that strings of bounded VC dimension are meagre in the topology of the reals, provide simple rules for bounding the VC dimension of a string, and show that the bi-infinite strings of VC dimension $d$ are a non-sofic shift space. Additionally we characterize the irreducible strings of low VC dimension (0,1 and 2), and provide connections to mathematical logic. - Open Access
Some new maximum VC classes
Set systems of finite VC dimension are frequently used in applications relating to machine learning theory and statistics. Two simple types of VC classes which have been widely studied are the maximum classes (those which are extremal with respect to Sauer's lemma) and so-called Dudley classes, which arise as sets of positivity for linearly parameterized functions. These two types of VC class were related by Floyd, who gave sufficient conditions for when a Dudley class is maximum. It is widely known that Floyd's condition applies to positive Euclidean half-spaces and certain other classes, such as sets of positivity for univariate polynomials. In this paper we show that Floyd's lemma applies to a wider class of linearly parameterized functions than has been formally recognized to date. In particular we show that, modulo some minor technicalities, the sets of positivity for any linear combination of real analytic functions is maximum on points in general position. This includes sets of positivity for multivariate polynomials as a special case.
Open AccessSome new maximum VC classes
Set systems of finite VC dimension are frequently used in applications relating to machine learning theory and statistics. Two simple types of VC classes which have been widely studied are the maximum classes (those which are extremal with respect to Sauer's lemma) and so-called Dudley classes, which arise as sets of positivity for linearly parameterized functions. These two types of VC class were related by Floyd, who gave sufficient conditions for when a Dudley class is maximum. It is widely known that Floyd's condition applies to positive Euclidean half-spaces and certain other classes, such as sets of positivity for univariate polynomials. In this paper we show that Floyd's lemma applies to a wider class of linearly parameterized functions than has been formally recognized to date. In particular we show that, modulo some minor technicalities, the sets of positivity for any linear combination of real analytic functions is maximum on points in general position. This includes sets of positivity for multivariate polynomials as a special case.
- Open Access
Vapnik-Chervonenkis density on indiscernible sequences, stability, and the maximum property
This paper presents some finite combinatorics of set systems with applications to model theory, particularly the study of dependent theories. There are two main results. First, we give a way of producing lower bounds on VC_ind-density, and use it to compute the exact VC_ind- density of polynomial inequalities, and a variety of geometric set families. The main technical tool used is the notion of a maximum set system, which we juxtapose to indiscernibles. In the second part of the paper we give a maximum set system analogue to Shelah's characterization of stability using indiscernible sequences.
Open AccessVapnik-Chervonenkis density on indiscernible sequences, stability, and the maximum property
This paper presents some finite combinatorics of set systems with applications to model theory, particularly the study of dependent theories. There are two main results. First, we give a way of producing lower bounds on VC_ind-density, and use it to compute the exact VC_ind- density of polynomial inequalities, and a variety of geometric set families. The main technical tool used is the notion of a maximum set system, which we juxtapose to indiscernibles. In the second part of the paper we give a maximum set system analogue to Shelah's characterization of stability using indiscernible sequences.
- Open Access
Dp-rank and forbidden configurations
A theory $T$ is shown to have an ICT pattern of depth $k$ in variables $\xbar$ iff it interprets some $k$-maximum VC class in $|\xbar|$ parameters.Open AccessDp-rank and forbidden configurations
A theory $T$ is shown to have an ICT pattern of depth $k$ in variables $\xbar$ iff it interprets some $k$-maximum VC class in $|\xbar|$ parameters. - 18 June 2009
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 43 (4) , 914-926
Compression Schemes, Stable Definable Families, and o-Minimal Structures
- 18 June 2009
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 43 (4) , 914-926
Compression Schemes, Stable Definable Families, and o-Minimal Structures