wiki_research

commit 8f1d577c16f1fe01112dfc62fc5beb60040ffdd2
parent e5455ca4dcab1c4cf89093d8e85bc13d8b53da5a
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed, 28 Jan 2026 18:01:39 +0100

commit with codex

Diffstat:
backurs2016which
 | 
2
+-
dual_graph
 | 
4
+++-
graph_basic_notions
 | 
2
++
incidence_graph
 | 
4
+++-
las_vegas_algorithm
 | 
13
+++++++++++++
line_graph
 | 
2
+-
monte_carlo_algorithm
 | 
13
+++++++++++++
square
 | 
2
++

8 files changed, 38 insertions(+), 4 deletions(-)
diff --git a/backurs2016which b/backurs2016which
@@ -6,4 +6,4 @@ uses [strong_exponential_time_hypothesis] and [orthogonal_vectors]
 
 Up: [academic_paper] on [regular_expression_matching]
 
-See also: [Ov_to_regular_expression_matching]
+See also: [Ov_to_regular_expression_matching], [backurs_indyk]
diff --git a/dual_graph b/dual_graph
@@ -1,11 +1,13 @@
 # Dual graph
 
-[graph_undirected]:
+An [undirected_graph] constructed from a [CNF]:
 - [vertices] are [clauses]
 - [edges] connect two [clauses] that share a [variable]
 
 if [conjunctive_normal_form] has unbounded [degree] then contains a large [clique]
 
+There is also a notion of dual graph for [planar_graphs], cf https://en.wikipedia.org/wiki/Dual_graph
+
 Up: [graph_undirected] of [conjunctive_normal_form]
 
 See also: [primal_graph], [incidence_graph], [dual_treewidth]
diff --git a/graph_basic_notions b/graph_basic_notions
@@ -30,6 +30,8 @@
   - [adjacency_matrix]
   - [adjacency_list]
 - [line_graph]
+  - [dual_graph]
+  - [incidence_graph]
 - [balanced_separator]
 - [graph_product]
 
diff --git a/incidence_graph b/incidence_graph
@@ -1,10 +1,12 @@
 # Incidence graph
 
-[graph_bipartite]:
+A [bipartite_graph] constructed from a [CNF]
 - left vertices are [variables]
 - right vertices are [clauses]
 - edge connects variable to clause if variable occurs in clause
 
+Can be defined also from a [graph], or from a [hypergraph]
+
 Up: [graph_bipartite], [conjunctive_normal_form]
 
 See also: [primal_graph], [dual_graph], [incidence_treewidth]
diff --git a/las_vegas_algorithm b/las_vegas_algorithm
@@ -0,0 +1,13 @@
+# Las vegas algorithm
+
+https://en.wikipedia.org/wiki/Las_Vegas_algorithm
+
+always gives correct answer, but running time is random
+
+expected running time is finite
+
+Corresponds to the class [ZPP] (for [polynomial_time] [algorithms])
+
+Up: [algorithm_randomized]
+
+See also: [monte_carlo_algorithm]
diff --git a/line_graph b/line_graph
@@ -10,4 +10,4 @@ They have a [Hamiltonian_cycle] if the original graph has a [Hamiltonian_cycle]:
 
 Up: [graph_basic_notions]
 
-See also: [dual_hypergraph]
+See also: [dual_hypergraph], [dual_graph], [incidence_graph]
diff --git a/monte_carlo_algorithm b/monte_carlo_algorithm
@@ -0,0 +1,13 @@
+# Monte carlo algorithm
+
+https://en.wikipedia.org/wiki/Monte_Carlo_algorithm
+
+sometimes gives wrong answers
+
+Corresponds to the classes:
+- [RP] (for [polynomial_time] [algorithms]) with [one_sided_error]
+- [BPP] (for [polynomial_time] [algorithms]) with [two_sided_error]
+
+Up: [algorithm_randomized]
+
+See also: [las_vegas_algorithm]
diff --git a/square b/square
@@ -5,3 +5,5 @@
 Up: [geometry]
 
 See also: [squaring]
+
+Aliases: squares