A circuit complexity formulation of algorithmic information theory

DOI10.1016/J.PHYSD.2023.133925MaRDI QIDQ6090675zbMATH OpenOpenAlexFDO

Authors Cole Wyeth, C. Sturtivant

Publication date 17 November 2023

Published in Physica D (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2306.14087

zbMATH Keywords

Boolean functionsKolmogorov complexitycircuit complexitysequence predictionalgorithmic information theorysolomonoff induction

Mathematics Subject Classification ID

Computer science (68-XX) Information and communication theory, circuits (94-XX)

Abstract: Inspired by Solomonoffs theory of inductive inference, we propose a prior based on circuit complexity. There are several advantages to this approach. First, it relies on a complexity measure that does not depend on the choice of UTM. There is one universal definition for Boolean circuits involving an universal operation such as nand with simple conversions to alternative definitions such as and, or, and not. Second, there is no analogue of the halting problem. The output value of a circuit can be calculated recursively by computer in time proportional to the number of gates, while a short program may run for a very long time. Our prior assumes that a Boolean function, or equivalently, Boolean string of fixed length, is generated by some Bayesian mixture of circuits. This model is appropriate for learning Boolean functions from partial information, a problem often encountered within machine learning as "binary classification." We argue that an inductive bias towards simple explanations as measured by circuit complexity is appropriate for this problem.

Cites work

• scientific article; zbMATH DE number 2089364 (Why is no real title available?)
• scientific article; zbMATH DE number 3489016 (Why is no real title available?)
• scientific article; zbMATH DE number 2081089 (Why is no real title available?)
• scientific article; zbMATH DE number 2119662 (Why is no real title available?)
• A formal theory of inductive inference. Part I
• A philosophical treatise of universal induction
• A universal algorithm for sequential data compression
• An introduction to Kolmogorov complexity and its applications
• Approximating the smallest grammar
• Bayesian learning for neural networks
• Being Bayesian about network structure. A Bayesian approach to structure discovery in Bayesian networks
• Computational limitations on learning from examples
• Finite state complexity
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization

Cited in

(2)

• Some issues in the theory of optimal algorithms and informational complexity
• An information complexity approach to extended formulations

This page was built for publication: A circuit complexity formulation of algorithmic information theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6090675)