commit b60de1effc5516efdec845e641dd2064bb1cd692
parent d3cba66b4b4164ca3da9c0bb59b9d4a70a95d8e1
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 17 Apr 2025 16:59:35 +0200
commit with codex
Diffstat:
18 files changed, 65 insertions(+), 15 deletions(-)
diff --git a/algorithm_combinatorial b/algorithm_combinatorial
@@ -1,6 +1,7 @@
# Combinatorial algorithm
-Algorithms, e.g., for [matrix_multiplication] which try to exclude [strassens_algorithm], but it looks like there is not formal definition of the concept
+Algorithms, e.g., for [matrix_multiplication] which try to exclude [strassens_algorithm] (and its use of [subtraction])
+- but it looks like there is not formal definition of the concept
Up: [algorithms]
diff --git a/algorithm_randomized b/algorithm_randomized
@@ -14,6 +14,6 @@ Techniques used for randomized algorithms:
Up: [algorithms]
-See also: [fpras], [rp], [complexity_random], [randomness]
+See also: [fpras], [rp], [complexity_random], [randomness], [derandomization]
Aliases: randomized
diff --git a/batch_updates b/batch_updates
@@ -4,3 +4,5 @@
- [batch_update_technique]: using as a technique to design algorithms
Up: [incremental_maintenance]
+
+Aliases: bulk updates
diff --git a/boolean b/boolean
@@ -5,5 +5,7 @@
- [formula_boolean]
- [satisfiability_boolean]
- [boolean_semiring]
+- [true]
+- [false]
Up: [logic]
diff --git a/boolean_valuation b/boolean_valuation
@@ -0,0 +1,13 @@
+# Boolean valuation
+
+A [function] mapping a set X to [Boolean] values
+
+- can be used to [evaluate] a [Boolean_function]
+ - can be a [satisfying_valuation] of a [Boolean_function]
+ - or a [falsifying_valuation]
+
+Up: [function], [valuation], [boolean]
+
+See also: [boolean_function]
+
+Aliases: assignment, Boolean assignment, assignments, Boolean assignments
diff --git a/enumeration_paths b/enumeration_paths
@@ -1,7 +0,0 @@
-# Enumeration paths
-
-[Enumeration] of [paths] in a [graph]
-
-[Practice]: [peng2025hop]
-
-Up: [enumeration_graphs], [paths]
diff --git a/group b/group
@@ -10,8 +10,8 @@ Types of groups:
[Theorems]:
-- classification of [finite_simple_groups]
-- [feit_thompson] theorem
+- [Classification_of_finite_simple_groups]
+- [Feit_Thompson] theorem
Tools:
@@ -21,3 +21,5 @@ Tools:
Up: [algebraic_structure], [mathematics]
See also: [monoid], [group_language]
+
+Aliases: groups
diff --git a/guarded_fragment b/guarded_fragment
@@ -3,6 +3,7 @@
- [gf2]
- [gc2]: like [fo2] with [counting_quantifiers]
- [gck]
+- [guarded_TGD]
According to [cate2023craig], enjoys [finite_model_property] but not [craig_interpolation]
diff --git a/pathwidth b/pathwidth
@@ -6,6 +6,8 @@ like [treewidth] but for [tree_decomposition] which is a [path]
- [pathwidth_computation]
- [pathwidth_approximation]
+- [path_decomposition]
+
Up: [width_measure], [path]
See also: [treewidth], [path_excentricity], [obstruction], [treelength]
diff --git a/preprocessing b/preprocessing
@@ -4,6 +4,8 @@ Computation done before something else
Used in [enumeration_definition]
+- [linear_preprocessing]
+
Up: [enumeration_definition]
See also: [delay], [enumeration_phase]
diff --git a/satisfying_valuation b/satisfying_valuation
@@ -0,0 +1,9 @@
+# Satisfying valuation
+
+[Boolean_valuation] such that a [Boolean_function] [evaluates] to [true]
+
+Up: [boolean_valuation]
+
+Aliases: satisfying assignment, satisfying assignments
+
+See also: [satisfiability_boolean]
diff --git a/semigroup b/semigroup
@@ -6,6 +6,7 @@ Special cases:
- [monoid]
- [group]
+- [semigroup_cancellative]
Examples:
diff --git a/semigroup_cancellative b/semigroup_cancellative
@@ -0,0 +1,12 @@
+# Semigroup cancellative
+
+https://en.wikipedia.org/wiki/Cancellative_semigroup
+
+Only cancellative semigroups can embed into [groups], cf:
+https://en.wikipedia.org/wiki/Cancellative_semigroup#Embeddability_in_groups
+
+Up: [semigroup]
+
+Aliases: cancellative semigroup, cancellative semigroups
+
+See also: [cancellation]
diff --git a/simple_path b/simple_path
@@ -1,7 +1,9 @@
# Simple path
-path with no repeated vertices
+A [path] with no repeated [vertices]
Up: [path]
-See also: [trail]
+See also: [trail], [walk]
+
+Aliases: simple paths
diff --git a/strassens_algorithm b/strassens_algorithm
@@ -5,6 +5,8 @@ https://en.wikipedia.org/wiki/Strassen_algorithm
multiplication of 2 by 2 matrices can be done with 7 products instead of 8
- gives an algorithm because you can reapply it recursively
-works with integers, but not with [matrix_boolean] in [boolean_semiring]
+works with integers, but not with [matrix_boolean] in [boolean_semiring] (or not as-is)
+
+uses [subtraction], so works in a [ring] but not in a [semiring]: it is not a [combinatorial_algorithm]
Up: [matrix_multiplication]
diff --git a/triangle b/triangle
@@ -11,7 +11,8 @@ Variante: single-source triangle counting ?
- [sparse_triangle]
-See also: [matrix_multiplication], [ov_conjecture], [negative_triangle], [exact_triangle], [triangle_free_graph], [triangle_inequality]
+See also: [matrix_multiplication], [ov_conjecture], [negative_triangle], [exact_triangle], [triangle_free_graph], [triangle_inequality],
+[Loomis_Whitney]
Up: [graph]
diff --git a/triangle_detection b/triangle_detection
@@ -9,6 +9,9 @@ https://en.wikipedia.org/wiki/Triangle-free_graph#Triangle_finding_problem
- [itai1977finding]
- For [sparse_graphs], it is possible to do Otilde(m^{2omega/(omega+1)}) [alon1997finding]
- [triangle_detection_conjecture]
+- For [combinatorial_algorithms], the best known bounds are [cubic] up to [polylogarithmic] factors, and any [truly_subcubic] algorithm would imply a [truly_subcubic] algorithm for [Boolean_matrix_multiplication]
+ - cf [williams2018subcubic]
+ - cf https://people.csail.mit.edu/virgi/6.890/lecture2.pdf
Up: [computational_problem] on [graph], [conjunctive_query], [fine_grained_complexity_problems]
diff --git a/universality_automata_nondeterministic b/universality_automata_nondeterministic
@@ -3,6 +3,8 @@
[conp_complete] even on [unary_alphabet]:
- https://cs.stackexchange.com/a/97751
+The shortest rejected word of an automaton with O(n) states may be Omega(n 2^n): cf [ellul2005regular], Theorem 32
+
Up: [universality_automata], [automata_nondeterministic]
Aliases: NFA universality
