commit d3bcb5e3ca1bd8beab6c03ed99337eda63cae1fe
parent c779847075519b4d8ea55946748ac8e03bd3fbf4
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 7 Jan 2025 10:59:33 +0100
commit with codex
Diffstat:
2 files changed, 15 insertions(+), 11 deletions(-)
diff --git a/arithmetic_circuit b/arithmetic_circuit
@@ -1,8 +1,6 @@
# Arithmetic circuit
-A [circuit] having plus-gates and times-gates. The inputs to plus-gates have
-weights ([linear_combination]). Generally the function represented should be
-non-negative.
+A [circuit] having plus-gates and times-gates. The inputs to plus-gates have weights ([linear_combination]). Generally the function represented should be non-negative.
- allowing negative weights (-> subtraction) can have a superpolynomial impact on conciseness
- cf [positive_vs_monotone]
- "monotone arithmetic circuit": no negative weights
@@ -13,22 +11,20 @@ Conditions:
- [deterministic]
- [smoothness] / [smoothing]
-Arithmetic circuits *with positive weights* can be translated to a
-[boolean_circuit] while preserving struural restrictions. Thus, for arithmetic functions whose support is a
-hard boolean function, we can leverage lower bounds on the [boolean_circuit] size
-to get a bound on the arithmetic circuit size
+Arithmetic circuits *with positive weights* can be translated to a [boolean_circuit] while preserving struural restrictions. Thus, for arithmetic functions whose support is a hard boolean function, we can leverage lower bounds on the [boolean_circuit] size to get a bound on the arithmetic circuit size
Can use [rank] technique for lower bound, using [communication_complexity]
- but [arithmetic_rectangle] instead of [combinatorial_rectangle]
-closure:
+[closure]:
-- we can represent the product of two structured circuits as a structured circuit
-if they are structured along the same [vtree]
-- conditioning: we can fix the value of a gate and preserve decomposability etc.
+- we can represent the product of two structured circuits as a structured circuit if they are structured along the same [vtree]
+- [conditioning]: we can fix the value of a gate and preserve decomposability etc.
[depth_reduction_arithmetic_circuit]
Up: [circuit]
See also: [circuit_algebraic]
+
+Aliases: arithmetic circuits
diff --git a/knowledge_compilation_query b/knowledge_compilation_query
@@ -0,0 +1,8 @@
+# Knowledge compilation query
+
+- [satisfiability]
+- [sharp_satisfiability]
+- [max_sat]
+- expressive [queries] like [weighted_maximum_model_counting]: [bannach2025weighted]
+
+Up: [knowledge_compilation], [query]
