Binary strings of finite VC dimension

• URL: http://arxiv.org/abs/2101.06490v2
• Date: Sun, 24 Jan 2021 14:00:22 GMT
• Title: Binary strings of finite VC dimension
• Authors: Hunter R Johnson
• Abstract summary: In this paper we investigate subsets named by a predicate $P$ such that the relation $P(x+y)$ has finite VC dimension. 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-so shift space.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• CSPs with Few Alien Constraints [12.330326247154968]
  We consider CSP$(mathcalA cup mathcalB)$ where $mathcalA$ is a structure and $mathcalB$ is an alien structure. We establish connections and obtain transferable complexity results to several well-studied problems that previously escaped classification attempts.
  arXiv  Detail & Related papers  (2024-08-23T08:34:13Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• Generalization Properties of Decision Trees on Real-valued and Categorical Features [2.370481325034443]
  We revisit binary decision trees from the perspective of partitions of the data. We consider three types of features: real-valued, categorical ordinal and categorical nominal, with different split rules for each.
  arXiv  Detail & Related papers  (2022-10-18T21:50:24Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Understanding and Compressing Music with Maximal Transformable Patterns [0.0]
  We present an algorithm that discovers maximal patterns in a point set, $DinmathbbRk$. We also present a second algorithm that discovers the set of occurrences for each of these maximal patterns. We evaluate the new compression algorithm with three classes of differing complexity on the task of classifying folk-song melodies into tune families.
  arXiv  Detail & Related papers  (2022-01-26T17:47:26Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Scattering data and bound states of a squeezed double-layer structure [77.34726150561087]
  A structure composed of two parallel homogeneous layers is studied in the limit as their widths $l_j$ and $l_j$, and the distance between them $r$ shrinks to zero simultaneously. The existence of non-trivial bound states is proven in the squeezing limit, including the particular example of the squeezed potential in the form of the derivative of Dirac's delta function. The scenario how a single bound state survives in the squeezed system from a finite number of bound states in the finite system is described in detail.
  arXiv  Detail & Related papers  (2020-11-23T14:40:27Z)
• Invariant subspaces of two-qubit quantum gates and their application in the verification of quantum computers [0.0]
  We investigate the groups generated by the sets of $CP$, $CNOT$ and $SWAPalpha$ (power-of-SWAP) quantum gate operations acting on $n$ qubits. We are able to determine the invariant subspaces of the $n-$qubit Hilbert space under the action of each group.
  arXiv  Detail & Related papers  (2020-09-08T11:22:43Z)
• A deep network construction that adapts to intrinsic dimensionality beyond the domain [79.23797234241471]
  We study the approximation of two-layer compositions $f(x) = g(phi(x))$ via deep networks with ReLU activation. We focus on two intuitive and practically relevant choices for $phi$: the projection onto a low-dimensional embedded submanifold and a distance to a collection of low-dimensional sets.
  arXiv  Detail & Related papers  (2020-08-06T09:50:29Z)
• VC-dimensions of nondeterministic finite automata for words of equal length [2.099922236065961]
  Let $NFA_b(q)$ denote the set of languages accepted by nondeterministic finite automata with $q$ states over an alphabet with $b$ letters. Let $B_n$ denote the set of words of length $n$.
  arXiv  Detail & Related papers  (2020-01-07T22:49:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.