Skip to Main content Skip to Navigation
New interface
Conference papers

A Compilation of Succinctness Results for Arithmetic Circuits

Abstract : Arithmetic circuits (AC) are circuits over the real numbers with 0/1-valued input variables whose gates compute the sum or the product of their inputs. Positive AC -- that is, AC representing non-negative functions -- subsume many interesting probabilistic models such as probabilistic sentential decision diagram (PSDD) or sum-product network (SPN) on indicator variables. Efficient algorithms for many operations useful in probabilistic reasoning on these models critically depend on imposing structural restrictions to the underlying AC. Generally, adding structural restrictions yields new tractable operations but increases the size of the AC. In this paper we study the relative succinctness of classes of AC with different combinations of common restrictions. Building on existing results for Boolean circuits, we derive an unconditional succinctness map for classes of monotone AC -- that is, AC whose constant labels are non-negative reals -- respecting relevant combinations of the restrictions we consider. We extend a small part of the map to classes of positive AC. Those are known to generally be exponentially more succinct than their monotone counterparts, but we observe here that for so-called deterministic circuits there is no difference between the monotone and the positive setting which allows us to lift some of our results. We end the paper with some insights on the relative succinctness of positive AC by showing exponential lower bounds on the representations of certain functions in positive AC respecting structured decomposability.
Document type :
Conference papers
Complete list of metadata

https://hal-univ-artois.archives-ouvertes.fr/hal-03517923
Contributor : Alexis de Colnet Connect in order to contact the contributor
Submitted on : Saturday, January 8, 2022 - 2:54:18 PM
Last modification on : Sunday, January 9, 2022 - 3:29:28 AM

Links full text

Identifiers

  • HAL Id : hal-03517923, version 1
  • ARXIV : 2110.13014

Collections

Citation

Alexis de Colnet, Stefan Mengel. A Compilation of Succinctness Results for Arithmetic Circuits. 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Nov 2021, Online Event, Vietnam. ⟨hal-03517923⟩

Share

Metrics

Record views

15