3 papers
cs.CC2021
A Compilation of Succinctness Results for Arithmetic Circuits
Alexis de Colnet, Stefan Mengel
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 r…
cs.CC2021
Characterizing Tseitin-formulas with short regular resolution refutations
Alexis de Colnet, Stefan Mengel
Tseitin-formulas are systems of parity constraints whose structure is described by a graph. These formulas have been studied extensively in proof complexity as hard instances in ma…
cs.AI2020
Lower Bounds for Approximate Knowledge Compilation
Alexis de Colnet, Stefan Mengel
Knowledge compilation studies the trade-off between succinctness and efficiency of different representation languages. For many languages, there are known strong lower bounds on th…