wiki_research

commit a7bc0a624d3a07d99c05ff8f4c9b0d9f39576fef
parent 9a8fcce33a024331e3305000c5320006b9686e68
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Mon, 25 Aug 2025 18:10:25 +0200

commit with codex

Diffstat:
bruner2014computational
 | 
5
+++++
circuit
 | 
1
+
circuit_homogeneous
 | 
11
+++++++++++
homogeneous
 | 
7
+++++++
parity
 | 
1
+
parity_constraints
 | 
7
+++++++
permutation
 | 
1
+
permutation_pattern_matching
 | 
6
++++++
permutation_separable
 | 
7
+++++++
polynomial_homogeneous
 | 
2
+-

10 files changed, 47 insertions(+), 1 deletion(-)
diff --git a/bruner2014computational b/bruner2014computational
@@ -0,0 +1,5 @@
+# bruner2014computational
+
+subsumes [bruner2013w1]
+
+Up: [academic_paper] on [permutation_pattern_matching]
diff --git a/circuit b/circuit
@@ -16,6 +16,7 @@
 - [formula]
 - [circuit_monotone]
 - [circuit_positive]
+- [circuit_homogeneous]
 
 ## Problems
 
diff --git a/circuit_homogeneous b/circuit_homogeneous
@@ -0,0 +1,11 @@
+# Circuit homogeneous
+
+A [circuit] where, for each [gate], the [satisfying_assignments] of the [gate] have the same [Hamming_weight]
+
+Can be enforced on many [circuit_classes] by a kind of [product_construction]
+
+Cf also [amarilli2017circuit] Section B.2
+
+Up: [circuit], [homogeneous]
+
+Aliases: homogeneous circuit, homogeneous circuits
diff --git a/homogeneous b/homogeneous
@@ -0,0 +1,7 @@
+# Homogeneous
+
+- [Homogeneous_automaton]
+- [Homogeneous_polynomial]
+- [Homogeneous_circuit]
+
+Up: [mathematics]
diff --git a/parity b/parity
@@ -4,6 +4,7 @@
 - [parity_p]
 - [parity_fine_grained]
 - [sat_parity]
+- [parity_constraints]
 
 - [even]
 - [odd]
diff --git a/parity_constraints b/parity_constraints
@@ -0,0 +1,7 @@
+# Parity constraints
+
+Constraints on the [parity], e.g., for [path_lengths]
+
+Generalization: [modularity_constraints]
+
+Up: [parity]
diff --git a/permutation b/permutation
@@ -16,6 +16,7 @@
 
 - [transposition]
 - [circular_permutation]
+- [permutation_separable]
 
 ## Variants
 
diff --git a/permutation_pattern_matching b/permutation_pattern_matching
@@ -7,6 +7,12 @@
 [stanley_wilf_conjecture]
 - [conjecture] on the proportion of [permutations] which [permutation_avoid] a [permutation_pattern]
 
+Generalizations:
+- with [vincular] patterns: [W1_hard]
+  - cf [bruner2014computational]
+- with [parity_constraints]
+  - cf [ardevolmartinez2024parity]
+
 See also: [permutation], [vincular]
 
 Up: [pattern_matching], [permutation_pattern]
diff --git a/permutation_separable b/permutation_separable
@@ -0,0 +1,7 @@
+# Separable permutation
+
+See [neou2016pattern] for definitions. Ensures the tractability of [PPM], even with [vincular] patterns
+
+Up: [permutation]
+
+Aliases: separable permutation
diff --git a/polynomial_homogeneous b/polynomial_homogeneous
@@ -5,6 +5,6 @@ A [multivariate_polynomial] whose nonzero terms all have the same [degree]
 
 https://en.wikipedia.org/wiki/Homogeneous_polynomial
 
-Up: [polynomial]
+Up: [polynomial], [homogeneous]
 
 Aliases: homogeneous polynomial