A circuit complexity formulation of algorithmic information theory

DOI10.1016/J.PHYSD.2023.133925arXiv2306.14087OpenAlexW4387026877MaRDI QIDQ6090675FDOQ6090675

Authors: Cole Wyeth, C. Sturtivant 

Publication date: 17 November 2023

Published in: Physica D (Search for Journal in Brave)

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.

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)

Cites Work

• Being Bayesian about network structure. A Bayesian approach to structure discovery in Bayesian networks
• Approximating the smallest grammar
• Title not available (Why is that?)
• A formal theory of inductive inference. Part I
• Finite state complexity
• Title not available (Why is that?)
• A universal algorithm for sequential data compression
• An introduction to Kolmogorov complexity and its applications
• Computational limitations on learning from examples
• Bayesian learning for neural networks
• A philosophical treatise of universal induction
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)