wiki_research

commit ab186f70a0c9fc4ec635667dc2c269ebdbc50297
parent 073b57210df08ce39420b87bb0652bbaf28b61d0
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed, 19 Feb 2025 17:31:06 +0100

commit with codex

Diffstat:
approximation
 | 
6
+++---
datalog_monadic
 | 
2
++
functional_dependency
 | 
2
+-
functional_dependency_approximate
 | 
6
+++---
grid_graph
 | 
2
++
independent_set
 | 
2
+-

6 files changed, 12 insertions(+), 8 deletions(-)
diff --git a/approximation b/approximation
@@ -12,8 +12,8 @@ Complexity classes [approximation_class]:
 Problems: [approximation_problems]
 
 Reasons not to get it:
-- conditional inapproximability [fpras_vs_npc]: no FPRAS if the [decision_problem] "décision =0" is [np_hard], unless you have [nptime] = [bpp] or [nptime] = [rp]
-- [sharp_is]: no FPRAS to count the [independent_set] of a [graph]
+- conditional inapproximability [fpras_vs_npc]: no [FPRAS] if the [decision_problem] "décision =0" is [np_hard], unless you have [nptime] = [bpp] or [nptime] = [rp]
+- [sharp_is]: no [FPRAS] to count the [independent_sets] of a [graph]
 - no [FPRAS] for [monotone2cnf] ([calautti2022query]), cf [sharp_satisfiability_fpras]
 - [hardness_of_approximation]
 
@@ -33,4 +33,4 @@ Other notions:
 
 Up: [research_directions]
 
-Aliases: approximate counting
+Aliases: approximate counting, approximated
diff --git a/datalog_monadic b/datalog_monadic
@@ -2,6 +2,8 @@
 
 [Datalog] where all [intensional_predicates] are [monadic]
 
+- [datalog_monadic_linear]
+
 Up: [datalog]
 
 Aliases: Monadic Datalog
diff --git a/functional_dependency b/functional_dependency
@@ -26,4 +26,4 @@
 
 Up: [equality_generating_dependency]
 
-Aliases: FD, FDs
+Aliases: FD, FDs, functional dependencies
diff --git a/functional_dependency_approximate b/functional_dependency_approximate
@@ -1,8 +1,8 @@
 # Functional dependency approximate
 
-- Survey with real-world study: parciak2023measuring
-- approximate implication: kenig2019integrity
+- Survey with real-world study: [parciak2023measuring]
+- approximate implication: [kenig2019integrity]
 
 Tags: #wikipedia
 
-Up: [functional_dependency]
+Up: [functional_dependency], [approximation]
diff --git a/grid_graph b/grid_graph
@@ -7,3 +7,5 @@
 Up: [graph_family]
 
 See also: [wall_graph]
+
+Aliases: grid graphs
diff --git a/independent_set b/independent_set
@@ -33,4 +33,4 @@ See also: [matching], [vertex_cover]
 
 Up: [graph_substructure]
 
-Aliases: coclique, anticlique
+Aliases: coclique, anticlique, independent sets, cocliques, anticliques