wiki_research

commit 533439e72f6ac1aadf66efec312f888fb3a5f87d
parent 44dc711c1df541421cb188890ff058efa6c77829
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Mon, 17 Nov 2025 17:04:04 +0100

Merge remote-tracking branch 'origin/master'

Diffstat:
apsp_reduces_to_distance_product
 | 
9
+++------
distance_product
 | 
6
+++++-
first_order_model_checking
 | 
2
+-
min_plus_product
 | 
7
-------

4 files changed, 9 insertions(+), 15 deletions(-)
diff --git a/apsp_reduces_to_distance_product b/apsp_reduces_to_distance_product
@@ -1,10 +1,7 @@
 # APSP reduces to distance product
 
-[fine_grained_reduction] from [all_pairs_shortest_path] to computing [distance_product]
+[fine_grained_reduction] from [APSP] to computing [distance_product]
 
-Take [adjacency_matrix] of a [graph], do [fast_exponentiation] to get the weight of
-the [shortest_path] of <= n edges
+Take [adjacency_matrix] of a [graph], do [fast_exponentiation] to get the weight of the [shortest_path] of <= n edges
 
-
-
-Up: [reduction] from [all_pair_shortest_path] to [distance_product]
+Up: [reduction] from [APSP] to [distance_product]
diff --git a/distance_product b/distance_product
@@ -3,11 +3,15 @@
 Given two [adjacency_matrices] A and B their *distance product* is
 (A*B)[i,j ] defined to be min_k (A[i,k ] + B[k,j ])
 - this is [matrix_multiplication] in the [tropical_semiring]
+- no known [subcubic_matrix_multiplication] algorithms
+  - but cf [williams2014faster], [williams2020truly]...
 
 [APSP_reduces_to_distance_product]
 
 Computing the distance product reduces to [negative_triangle]
 
-See also: [all_pairs_shortest_path]
+See also: [all_pairs_shortest_path], [mpp_minimum]
 
 Aliases: min plus product, min-plus product
+
+Up: [matrix_multiplication]
diff --git a/first_order_model_checking b/first_order_model_checking
@@ -23,4 +23,4 @@ Up: [model_checking] for [first_order_logic]
 
 See also: [fine_grained_complexity], [clique_problem]
 
-Aliases: FO model checking
+Aliases: FO model checking, FO evaluation, first order evaluation, first-order evaluation
diff --git a/min_plus_product b/min_plus_product
@@ -1,7 +0,0 @@
-# Min plus product
-
-The [matrix_product] but in the [tropical_semiring]
-
-See also: [mpp_minimum]
-
-Up: [operation] on [matrices]