commit 9efdb225d639097f6ed9425d9a3bb1d162623b65
parent 6db52342590b12e32f3981d7cd7e6a8f836b318a
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 4 Feb 2025 14:20:51 +0100
commit with codex
Diffstat:
9 files changed, 69 insertions(+), 6 deletions(-)
diff --git a/approximation b/approximation
@@ -25,7 +25,11 @@ Applications:
Notion of [reduction]: [approximation_preserving_reduction]
-Other notion: [query_approximation]
+Other notions:
+
+- [query_approximation]
+- [approximate_aggregation]
+- [query_evaluation_approximate]
Up: [research_directions]
diff --git a/conjunctive_normal_form b/conjunctive_normal_form
@@ -9,6 +9,7 @@ Types:
- [3cnf]
- [kcnf]
- [cnf_variable_convex]
+- [hitting_cnf]
lower bound on size of CNF relative to [disjunctive_normal_form]
diff --git a/disjunctive_normal_form_orthogonal b/disjunctive_normal_form_orthogonal
@@ -1,14 +1,14 @@
# Disjunctive normal form orthogonal
-[disjunctive_normal_form] where for any two "terms" they are not mutually satisfiable
-(so it is an [unambiguous] [disjunctive_normal_form])
+[disjunctive_normal_form] where for any two [terms] they are not mutually satisfiable
+- so it is an [unambiguous] [disjunctive_normal_form]
-Could be called "unambiguous DNF"
-
-What is the complement called? it's a [conjunctive_normal_form] where the disjunction of any two clauses is tautological
+[complement]: [hitting_cnf]
note that necessarily the clauses (all except at most one) must be big (at least n/2) to satisfy this condition
[disjunctive_normal_form_orthogonal_negation]
Up: [disjunctive_normal_form]
+
+Aliases: unambiguous DNF, unambiguous DNFs
diff --git a/hitting_cnf b/hitting_cnf
@@ -0,0 +1,9 @@
+# Hitting cnf
+
+A [conjunctive_normal_form] where the [disjunction] of any two [clauses] is [tautological]
+
+[Negation]: [disjunctive_normal_form_orthogonal]
+
+Up: [conjunctive_normal_form]
+
+See also: [hitting_set]
diff --git a/negation b/negation
@@ -0,0 +1,12 @@
+# Negation
+
+- [negation_semantics]
+- [stratification]
+- [guarded_negation]
+- [datalog_negation]
+- [negation_as_failure]
+- [first_order_logic_existential_positive]
+
+Up: [logic]
+
+Aliases: negated
diff --git a/sampling b/sampling
@@ -0,0 +1,16 @@
+# Sampling
+
+- [cardinality_estimation]
+- [uniform_sampling]
+- [sampling_query_answers]
+ - [sampling_cqs]
+- [sampling_approximate]
+- [monte_carlo]
+- [coupon_collector_problem]
+- [german_tank_problem]
+- [square_root_biaised_sampling]
+- [sampling_subgraph]
+
+Up: [algorithms]
+
+See also: [approximation]
diff --git a/square_root_biaised_sampling b/square_root_biaised_sampling
@@ -0,0 +1,7 @@
+# Square root biaised sampling
+
+https://en.m.wikipedia.org/wiki/Square_root_biased_sampling
+
+sampling to find dangerous individuals using the [square_root] of [priors]
+
+Up: [sampling]
diff --git a/stratification b/stratification
@@ -0,0 +1,7 @@
+# Stratification
+
+Useful for [datalog_aggregation] or [datalog_negation]
+
+Up: [datalog]
+
+See also: [Datalog_stratified]
diff --git a/uniform_sampling b/uniform_sampling
@@ -0,0 +1,7 @@
+# Uniform sampling
+
+[sampling] from [uniform_distribution]
+
+[FPAUS]: fully-polynomial almost uniform sampler
+
+Up: [sampling]
