wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

commit e47158fd7edb1be3dc77243197e70e84270a586c
parent c7c83bddd3f08de9ef2026316bdc68816f602106
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Sat, 11 Jan 2025 20:15:48 +0100

Merge branch 'master' of a3nm.net:git/wiki_research

Diffstat:
2rpq | 9+++++++++
adjacency_matrix | 2+-
approximation | 6++++--
arithmetic_circuit | 18+++++++-----------
average_degree | 5+++++
boolean_circuit | 2++
boolean_formula | 4+++-
c2rpq | 4+++-
certain_answers | 9+++++++++
circuit | 2++
circuit_equivalence | 5+++++
cnf_variable_convex | 9+++++++++
cograph | 6+++++-
computational_social_choice | 6++++++
conjunctive_normal_form | 2++
conjunctive_query_boolean | 5+++++
conjunctive_query_full | 7+++++++
convexity | 8++++++++
craig_interpolation | 3++-
crossing_number | 11+++++++++++
crossing_number_inequality | 7+++++++
database_repairs | 2+-
database_theory_concepts | 1+
datalog_nonrecursive | 9+++++++++
ddnnf | 2++
degree | 1+
dynamic_connectivity_practice | 5+++++
edge_contraction | 9+++++++++
equation | 2+-
equisatisfiability | 2++
equivalence | 8++------
equivalence_problem | 11+++++++++++
eulers_formula | 9+++++++++
even_hole_free_graph | 4++--
extremal_graph_theory | 2++
forbidden_graph_characterization | 14++++++++++++++
forbidden_subgraph_problem | 7+++++++
function | 2++
graph_free | 11+++++++++++
graph_h_free | 12++++++++++++
graph_h_minor_free | 11+++++++++++
graph_induced_h_free | 11+++++++++++
graph_isomorphism | 2++
graph_minor | 6+++---
graph_p5_free | 7+++++++
graph_pk_free | 15+++++++++++++++
graph_sparse | 9+++++++++
gray_code | 2++
grid_minor | 1+
independent_set | 6+++++-
induced_minor | 9+++++++++
induced_subgraph | 4+++-
k_relation | 4+++-
knowledge_compilation | 1+
knowledge_compilation_query | 8++++++++
literal | 2++
mathematics | 6++++++
mathematics_fields | 1+
planar_graph | 15+++++++++++----
positive_threshold_function | 7+++++++
probabilistic_circuit | 2+-
probability_distribution | 9+++++++++
provenance_panda | 5+++++
query | 4++++
query_boolean | 11+++++++++++
query_full | 9+++++++++
query_language | 2++
query_recursive | 10++++++++++
ramsey_theorem | 4+++-
representation | 8++++++++
satisfiability_weighted | 3+--
semantic_treewidth | 17+++++++++++++++++
spanning_tree | 2++
statistics | 6++++++
subgraph | 7+++++++
submodular_approximation | 5+++++
submodular_function | 9+++++++++
submodular_optimization | 3++-
submodular_set_function | 2+-
theorem | 2++
threshold | 7+++++++
tree_even | 13+++++++++++++
tree_odd | 11+++++++++++
triangle_free_graph | 4+++-
tseytin_transformation | 7+++++++
uc2rpq | 9++++++---
uncertain_data | 6++++++
87 files changed, 499 insertions(+), 48 deletions(-)

diff --git a/2rpq b/2rpq @@ -0,0 +1,9 @@ +# 2RPQs + +A [generalization] of [RPQs] where we allow inverse predicates + +Generalization: [C2RPQs] + +Up: [graph_query_languages], [regular_path_query] + +Aliases: 2RPQs diff --git a/adjacency_matrix b/adjacency_matrix @@ -11,4 +11,4 @@ Up: [graph_representation] Aliases: adjacency matrices -See also: [adjacency_list] +See also: [adjacency_list], [adjacent] diff --git a/approximation b/approximation @@ -1,7 +1,7 @@ # Approximation Two kinds of approximation: -- [approximation_additive]: section 3.2.1 souihli2012querying [monte_carlo] [hoeffdings_inequality] +- [approximation_additive]: section 3.2.1 [souihli2012querying] [monte_carlo] [hoeffdings_inequality] - [approximation_multiplicative]: what follows is about those Complexity classes [approximation_class]: @@ -14,7 +14,7 @@ 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] -- no [FPRAS] for [monotone2cnf] (calautti2022query), cf [sharp_satisfiability_fpras] +- no [FPRAS] for [monotone2cnf] ([calautti2022query]), cf [sharp_satisfiability_fpras] - [hardness_of_approximation] Applications: @@ -25,6 +25,8 @@ Applications: Notion of [reduction]: [approximation_preserving_reduction] +Other notion: [query_approximation] + Up: [research_directions] Aliases: approximate counting diff --git a/arithmetic_circuit b/arithmetic_circuit @@ -1,8 +1,6 @@ # Arithmetic circuit -A [circuit] having plus-gates and times-gates. The inputs to plus-gates have -weights ([linear_combination]). Generally the function represented should be -non-negative. +A [circuit] having plus-gates and times-gates. The inputs to plus-gates have weights ([linear_combination]). Generally the function represented should be non-negative. - allowing negative weights (-> subtraction) can have a superpolynomial impact on conciseness - cf [positive_vs_monotone] - "monotone arithmetic circuit": no negative weights @@ -13,22 +11,20 @@ Conditions: - [deterministic] - [smoothness] / [smoothing] -Arithmetic circuits *with positive weights* can be translated to a -[boolean_circuit] while preserving struural restrictions. Thus, for arithmetic functions whose support is a -hard boolean function, we can leverage lower bounds on the [boolean_circuit] size -to get a bound on the arithmetic circuit size +Arithmetic circuits *with positive weights* can be translated to a [boolean_circuit] while preserving struural restrictions. Thus, for arithmetic functions whose support is a hard boolean function, we can leverage lower bounds on the [boolean_circuit] size to get a bound on the arithmetic circuit size Can use [rank] technique for lower bound, using [communication_complexity] - but [arithmetic_rectangle] instead of [combinatorial_rectangle] -closure: +[closure]: -- we can represent the product of two structured circuits as a structured circuit -if they are structured along the same [vtree] -- conditioning: we can fix the value of a gate and preserve decomposability etc. +- we can represent the product of two structured circuits as a structured circuit if they are structured along the same [vtree] +- [conditioning]: we can fix the value of a gate and preserve decomposability etc. [depth_reduction_arithmetic_circuit] Up: [circuit] See also: [circuit_algebraic] + +Aliases: arithmetic circuits diff --git a/average_degree b/average_degree @@ -0,0 +1,5 @@ +# Average degree + +The [average] of the [degree] of [vertices] in a [graph] + +Up: [degree], [average] diff --git a/boolean_circuit b/boolean_circuit @@ -10,3 +10,5 @@ Similar: https://en.wikipedia.org/wiki/Propositional_directed_acyclic_graph Up: [circuit] See also: [boolean_formula], [knowledge_compilation_classes] + +Aliases: Boolean circuits diff --git a/boolean_formula b/boolean_formula @@ -9,6 +9,8 @@ An [expression] which represents a [boolean_function], built from [literals] usi - [term] - [literal] -Up: [boolean_function] +Up: [representation] of [boolean_function] See also: [boolean_circuit], [knowledge_compilation_classes] + +Aliases: formula boolean diff --git a/c2rpq b/c2rpq @@ -1,7 +1,9 @@ # C2RPQ -conjunction of [2rpq] +[Query_conjunction] of [2RPQs] Generalization: [uc2rpq] Up: [graph_query_languages], [conjunctive_query], [2rpq], [crpq] + +Aliases: C2RPQs diff --git a/certain_answers b/certain_answers @@ -0,0 +1,9 @@ +# Certain answers + +Given a [query] Q and [uncertain_data] D, a *certain answer* is a [query_answer] which is true on every [possible_world] of D. If Q is a [Boolean_query], we talk about the query being certain + +- [gheerbrant2023querying] + +Up: [uncertain_data] + +Aliases: certain answer diff --git a/circuit b/circuit @@ -51,3 +51,5 @@ Up: [theoretical_computer_science] See also: [sum_product_network] + +Aliases: circuits diff --git a/circuit_equivalence b/circuit_equivalence @@ -0,0 +1,5 @@ +# Circuit equivalence + +[Computational_problem] of deciding, given two [Boolean_circuits], whether they represent the same [Boolean_function] + +Up: [equivalence], [circuit] diff --git a/cnf_variable_convex b/cnf_variable_convex @@ -0,0 +1,9 @@ +# Cnf variable convex + +defined in [bova2017compiling] + +Up: [conjunctive_normal_form] + +Aliases: variable convex CNF, variable convex formula + +See also: [convexity] diff --git a/cograph b/cograph @@ -2,6 +2,10 @@ https://en.wikipedia.org/wiki/Cograph -The class of cographs is the class of [graph] defined by starting from the single vertex graph and closing by the [complementation] and [disjoint_union] operations +The [graph_class] of *cographs* is the [graph_class] of [undirected_graphs] defined by starting from the [single_vertex_graph] and [graph_closing] by the [graph_complementation] and [graph_disjoint_union] [graph_operations]. + +Also called the P4-free graphs, cf [pk_free_graph]. Up: [graph_family] + +Aliases: cographs diff --git a/computational_social_choice b/computational_social_choice @@ -0,0 +1,6 @@ +# Computational social choice + +- [voting_systems] +- [preferences] + +Up: [computer_science_fields] diff --git a/conjunctive_normal_form b/conjunctive_normal_form @@ -2,11 +2,13 @@ A [boolean_formula] which is a [conjunction] of [clauses] +Types: - [monotone_cnf] - [2cnf] - [monotone2cnf] - [3cnf] - [kcnf] +- [cnf_variable_convex] lower bound on size of CNF relative to [disjunctive_normal_form] diff --git a/conjunctive_query_boolean b/conjunctive_query_boolean @@ -0,0 +1,5 @@ +# Conjunctive query boolean + +[conjunctive_query] with no [output_variable], all variables are [existentially_quantified] + +Up: [conjunctive_query], [query_boolean] diff --git a/conjunctive_query_full b/conjunctive_query_full @@ -0,0 +1,7 @@ +# Conjunctive query full + +A [CQ] without [projection]; also called a [join] query + +Up: [conjunctive_query], [query_full] + +Aliases: full conjunctive query, full CQ, full CQs diff --git a/convexity b/convexity @@ -0,0 +1,8 @@ +# Convexity + +- [convex_function] +- [convex_set] +- [convex_hull] +- [cnf_variable_convex] + +Up: [mathematics] diff --git a/craig_interpolation b/craig_interpolation @@ -2,7 +2,8 @@ For every [implication] φ => ψ, there is a formula χ using only the common [relation_symbol]s of φ and ψ such that φ => χ and χ => ψ -[cate2023craig]: [survey_article] on [craig_interpolation] for [guarded_fragment] +- [cate2023craig]: [survey_article] on [craig_interpolation] for [guarded_fragment] +- [cate2024craig]: [invited_talk] Up: [property] of [logical_fragment] diff --git a/crossing_number b/crossing_number @@ -0,0 +1,11 @@ +# Crossing number + +https://en.wikipedia.org/wiki/Crossing_number_(graph_theory) + +Lowest number of [edge] crossings of a [plane_embedding] of an [undirected_graph]. + +An [undirected_graph] is a [planar_graph] iff the crossing number is zero + +[crossing_number_inequality] + +Up: [planar_graph] diff --git a/crossing_number_inequality b/crossing_number_inequality @@ -0,0 +1,7 @@ +# Crossing number inequality + +https://en.wikipedia.org/wiki/Crossing_number_inequality + +lower bound on the [crossing_number] as a function of the number of [edges] and [vertices] + +Up: [crossing_number], [inequality] diff --git a/database_repairs b/database_repairs @@ -4,7 +4,7 @@ [marconi2024consistent] -with [preference]s: [pardal2024computational] +with [preferences]: [pardal2024computational] - [repair_counting] diff --git a/database_theory_concepts b/database_theory_concepts @@ -11,5 +11,6 @@ - [query_containment] - [omqa] - [omqa_finite] vs [omqa_unrestricted] +- [tuple] Up: [database_theory] diff --git a/datalog_nonrecursive b/datalog_nonrecursive @@ -0,0 +1,9 @@ +# Datalog nonrecursive + +[Datalog] which is not [query_recursive] + +Equivalent in [expressiveness] to [UCQs], but there can be [sharing] of common subexpressions + +Up: [datalog] + +Aliases: nonrecursive Datalog diff --git a/ddnnf b/ddnnf @@ -2,6 +2,8 @@ [deterministic] [decomposable] [nnf] +testing [circuit_equivalence] of d-DNNFs is in [coRP]: [darwiche2002testing] + Up: [knowledge_compilation_classes], [dd] See also: [dnnf], [decision_dnnf], [uobdd] diff --git a/degree b/degree @@ -5,5 +5,6 @@ Number of [neighbors] of a [vertex] In [directed_graphs], we can distinguish the [indegree] and [outdegree], respectively the number of [vertices] having a edge to the [vertex], or from the [vertex] - [maximal_degree] +- [average_degree] Up: [graph_basic_notions] diff --git a/dynamic_connectivity_practice b/dynamic_connectivity_practice @@ -0,0 +1,5 @@ +# Dynamic connectivity practice + +[chen2025experimental] + +Up: [dynamic_connectivity], [practice] diff --git a/edge_contraction b/edge_contraction @@ -0,0 +1,9 @@ +# Edge contraction + +Given a [graph] G and an [edge] e, performing the *contraction* of e in G means merging the two [endpoints] e into one single vertex + +Up: [graph] + +Aliases: edge contractions, contraction, contractions + +See also: [contraction_sequence] diff --git a/equation b/equation @@ -9,4 +9,4 @@ Up: [mathematics] -See also: [disequation], [inequation] +See also: [disequation], [inequation], [equality] diff --git a/equisatisfiability b/equisatisfiability @@ -7,3 +7,5 @@ Two [logic_formulas] f and f' are equisatisfiable if f being satisfiable is [equ Up: [satisfiability] Aliases: equisatisfiable + +See also: [equivalence_problem] diff --git a/equivalence b/equivalence @@ -1,15 +1,11 @@ # Equivalence -As [computational_problem]: - -- [language_equivalence] -- [query_equivalence] -- [automaton_equivalence] -- [regular_expression_equivalence] +As [computational_problem]: [equivalence_problem] Other: - [equivalence_relation] +- [equivalence_operator] in [propositional_logic] Up: [mathematics] diff --git a/equivalence_problem b/equivalence_problem @@ -0,0 +1,11 @@ +# Equivalence problem + +- [language_equivalence] +- [query_equivalence] +- [automaton_equivalence] +- [regular_expression_equivalence] +- [circuit_equivalence] + +Up: [computational_problem], [equivalence] + +See also: [equisatisfiability] diff --git a/eulers_formula b/eulers_formula @@ -0,0 +1,9 @@ +# Euler's formula + +https://en.wikipedia.org/wiki/Euler_characteristic#Plane_graphs + +https://en.wikipedia.org/wiki/Planar_graph#Euler's_formula + +Up: [planar_graph] + +See also: [crossing_number_inequality] diff --git a/even_hole_free_graph b/even_hole_free_graph @@ -2,7 +2,7 @@ https://en.wikipedia.org/wiki/Even-hole-free_graph -A [graph_undirected] without [hole] of [even] length +An [undirected_graph] without [hole] of [even] length [survey_paper]: [vuskovic2010even] @@ -10,4 +10,4 @@ It is an [open_problem] whether [graph_coloring] or [maximum_independent_set] co Up: [undirected_graph], [hole], [graph_tractability] -See also: [graph_perfect], [even_cycle_free_graph] +See also: [graph_perfect], [even_cycle_free_graph], [graph_h_free] diff --git a/extremal_graph_theory b/extremal_graph_theory @@ -10,4 +10,6 @@ https://en.wikipedia.org/wiki/Extremal_graph_theory - [szemeredi_regularity_lemma] +- [forbidden_subgraph_problem] + Up: [extremal_combinatorics] on [graph] diff --git a/forbidden_graph_characterization b/forbidden_graph_characterization @@ -0,0 +1,14 @@ +# Forbidden graph characterization + +https://en.wikipedia.org/wiki/Forbidden_graph_characterization +(contains a list) + +Can be based on: + +- [subgraphs] +- [induced_subgraphs] +- [topological_minors] +- [minors], see [forbidden_minor] +- [induced_minors] + +See also: [graph_free] diff --git a/forbidden_subgraph_problem b/forbidden_subgraph_problem @@ -0,0 +1,7 @@ +# Forbidden subgraph problem + +https://en.wikipedia.org/wiki/Forbidden_subgraph_problem + +Largest number of [edges] in an n-[vertex] [undirected_graph] while being [graph_h_free] + +Up: [graph_h_free], [extremal_graph_theory] diff --git a/function b/function @@ -21,3 +21,5 @@ Notions: Up: [mathematics] See also: [functional_dependency] + +Aliases: functions diff --git a/graph_free b/graph_free @@ -0,0 +1,11 @@ +# Graph free + +An [undirected_graph] that does not have a certain kind of structure + +- [graph_induced_h_free] +- [graph_h_minor_free] +- [graph_h_free] + +Up: [graph_family] + +See also: [forbidden_graph_characterization] diff --git a/graph_h_free b/graph_h_free @@ -0,0 +1,12 @@ +# H-free graph + +An [undirected_graph] is *H-free* if it does not have an [undirected_graph] H as a [subgraph] + +Each [undirected_graph] H thus defines a [graph_family] + +- [triangle_free_graphs] +- [forbidden_subgraph_problem] + +Up: [graph_free] + +See also: [induced_h_free], [h_minor_free] diff --git a/graph_h_minor_free b/graph_h_minor_free @@ -0,0 +1,11 @@ +# H-minor-free graph + +An [undirected_graph] is *H-minor-free* if it does not have an [undirected_graph] H as a [graph_minor] + +Each [undirected_graph] H thus defines a [graph_family], which must be [sparse_graphs] + +discussed in https://en.wikipedia.org/wiki/Graph_minor + +Up: [graph_free] + +See also: [graph_h_free] diff --git a/graph_induced_h_free b/graph_induced_h_free @@ -0,0 +1,11 @@ +# induced-H-free graph + +An [undirected_graph] is *induced-H-free* if it does not have an [undirected_graph] H as an [induced_subgraph] + +Each [undirected_graph] H thus defines a [graph_family] + +- [graph_pk_free] + +Up: [graph_free] + +See also: [graph_h_free] diff --git a/graph_isomorphism b/graph_isomorphism @@ -5,3 +5,5 @@ Up: [isomorphism] of [graph] See also: [graph_homomorphism], [canonical_labeling], [weisfeiler_leman], [graph_automorphism] + +Aliases: graph isomorphic diff --git a/graph_minor b/graph_minor @@ -1,11 +1,11 @@ # Graph minor -- [contraction] +- [edge_contraction] [graph_minor_testing] Up: [graph] -See also: [robertson_seymour], [topological_minor], [excluded_minor] +See also: [robertson_seymour], [topological_minor], [excluded_minor], [forbidden_minor], [induced_minor] -Aliases: graph minors +Aliases: graph minors, minor, minors diff --git a/graph_p5_free b/graph_p5_free @@ -0,0 +1,7 @@ +# Graph p5 free + +https://www.graphclasses.org/classes/gc_396.html + +cf, e.g., [chudnowski2023cops] + +Up: [graph_pk_free] diff --git a/graph_pk_free b/graph_pk_free @@ -0,0 +1,15 @@ +# P_k-free graph + +An [undirected_graph] is *P_k-free* if it does not have an [induced_subgraph] which is [graph_isomorphic] to a [path] on k [vertices] + +- P_2-free means no [edge] at all, so [graph_empty], or [independent_set] +- P_3-free means every [connected_component] is a [clique] + - https://math.stackexchange.com/questions/3564039/describe-all-graphs-that-do-not-contain-p-3-as-an-induced-subgraph +- P_4-free are precisely the [cographs] +- P_5-free: [graph_p5_free] + +Up: [graph_family], [graph_h_free] + +Aliases: PK free graph + +See also: [forbidden_minor] diff --git a/graph_sparse b/graph_sparse @@ -0,0 +1,9 @@ +# Graph sparse + +https://en.wikipedia.org/wiki/Dense_graph + +An [undirected_graph] where the number of [edges] is o(n^2), for n the number of [vertices] + +Up: [graph_family] + +Aliases: sparse graph, sparse graphs diff --git a/gray_code b/gray_code @@ -5,6 +5,8 @@ - cf [minimal_absent_word] - older survey: [savage1997survey] +- [shuffle_exchange_network] [feldmann1996shuffle] + Up: [enumeration] See also: [middle_levels_conjecture], [torsten] diff --git a/grid_minor b/grid_minor @@ -5,6 +5,7 @@ relevant [academic_papers]: - [lanzinger2022complexity] - [chekuri2016polynomial] +- [chuzhoy2021towards] for tighter bounds on grid minor extraction used for [hardness] results, e.g., [grohe2007complexity] diff --git a/independent_set b/independent_set @@ -1,6 +1,8 @@ # Independent set -An independent set is a subset of vertices such that no two vertices of the subset are adjacent +https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29 + +An *independent set* is a [subset] of [vertices] of an [undirected_graph] such that no two [vertices] of the [subset] are [adjacent]. Also called a "coclique" or "anticlique". ## Connections @@ -30,3 +32,5 @@ By [duality], counting independent sets exactly is the same as counting [vertex_ See also: [matching], [vertex_cover] Up: [graph_substructure] + +Aliases: coclique, anticlique diff --git a/induced_minor b/induced_minor @@ -0,0 +1,9 @@ +# Induced minor + +https://en.wikipedia.org/wiki/Graph_minor#Induced_minors + +An [undirected_graph] H that can be obtained from an [undirected_graph] G by taking an [induced_subgraph] and then doing [edge_contractions] + +See also: [graph_minor] + +Aliases: induced minors diff --git a/induced_subgraph b/induced_subgraph @@ -1,7 +1,9 @@ # Induced subgraph -[subgraph] defined by taking a subset U of vertices and the edges between the vertices of U +A [subgraph] of a [graph] defined by taking a [subset] U of [vertices] and taking the [edges] between the [vertices] of U See also: [subgraph], [graph_minor], [induced_subhypergraph], [induced_cycle] Up: [graph] + +Aliases: induced subgraphs diff --git a/k_relation b/k_relation @@ -1,6 +1,6 @@ # K-relation -A [relation] where the [tuple]s are annotated by a value from a [semiring] +A [relation] where the [tuples] are annotated by a value from a [semiring] Used in: @@ -10,3 +10,5 @@ Used in: Up: [relation] with [semiring] See also: [database_instance] + +Aliases: k-relations, k_relations, k-relation diff --git a/knowledge_compilation b/knowledge_compilation @@ -6,6 +6,7 @@ Classes of [circuit] ensuring tractability - connections to [arithmetic_circuits] - [query_compilation]: knowledge compilation on the [provenance] of a query - [constraint_satisfaction_problem_knowledge_compilation] +- [knowledge_compilation_query]: the type of questions asked on circuits [circuit_bounds_vs_complexity_bounds] diff --git a/knowledge_compilation_query b/knowledge_compilation_query @@ -0,0 +1,8 @@ +# Knowledge compilation query + +- [satisfiability] +- [sharp_satisfiability] +- [max_sat] +- expressive [queries] like [weighted_maximum_model_counting]: [bannach2025weighted] + +Up: [knowledge_compilation], [query] diff --git a/literal b/literal @@ -3,3 +3,5 @@ Either a [variable] or the [negation] of a [variable] Up: [boolean_formula] + +Aliases: literals diff --git a/mathematics b/mathematics @@ -28,6 +28,8 @@ - [function] - [equation] - [equation_system] + - [inequation] + - [disequation] - [sequence] - [cartesian_product] - [plane_mathematics] @@ -44,6 +46,10 @@ - [infinite] - [cardinal] - [fourier_transform] +- [convexity] +- [equality] +- [inequality_mathematics] +- [disequality] ## Fields diff --git a/mathematics_fields b/mathematics_fields @@ -16,5 +16,6 @@ classification [msc] - [randomness] - [fourier_analysis] - [discrete_mathematics] +- [statistics] Up: [mathematics] diff --git a/planar_graph b/planar_graph @@ -1,6 +1,6 @@ # Planar graph -A [graph_undirected] that can be embedded on [plane_mathematics] +A [graph_undirected] that has a [plane_embedding], i.e., can be embedded on [plane_mathematics] - Recognizing them: [planarity_testing] - [dynamic_planarity_testing] @@ -9,18 +9,25 @@ A [graph_undirected] that can be embedded on [plane_mathematics] - open for [treewidth] - [planar_language] -[Theorem]s: +[Theorems]: - [Kuratowskis_theorem] in terms of [topological_minors] - [Wagners_theorem] in terms of [graph_minors] +Necessary conditions: + +- [Euler's_formula] + - implies that [average_degree] must be at most 6 + Specific algorithms: - [fkt_algorithm] -Generalizations to [hypergraph]s: [planar_hypergraph] +Generalizations: -Generalization: [directed_planar_graph] +- to [hypergraphs]: [planar_hypergraph] +- to [directed_graphs]: [directed_planar_graph] +- to quantify the "degree of non-planarity": [crossing_number] See also: [graph_drawing] diff --git a/positive_threshold_function b/positive_threshold_function @@ -0,0 +1,7 @@ +# Positive threshold function + +cf https://cstheory.stackexchange.com/questions/31469/which-monotone-boolean-functions-are-representable-as-thresholds-on-sums + +Up: [boolean_function_classes] + +See also: [threshold] diff --git a/probabilistic_circuit b/probabilistic_circuit @@ -23,7 +23,7 @@ we want to do [maximum_a_posteriori] on such circuits - md-vtrees: a way to guarantee marginal determinism, just by labeling v-tree nodes with a subset S of variables on which you have to be S-deterministic -connections to other kinds of polynomials than [probability_distribution]: see [broadrick2024polynomial] +connections to other kinds of [polynomials] than [probability_distributions]: see [broadrick2024polynomial] See also: [arithmetic_circuit], [circuit_algebraic] diff --git a/probability_distribution b/probability_distribution @@ -0,0 +1,9 @@ +# Probability distribution + +For a set of [probability_outcomes] of a [random_variable] X, a [probability_distribution] is a [function] giving a [probability] to every [probability_outcome] of X, so that the [probabilities] sum up to 1 ([normalization]) + +Up: [probabilities] + +See also: [measure] + +Aliases: probability distributions diff --git a/provenance_panda b/provenance_panda @@ -0,0 +1,5 @@ +# Provenance for PANDA + +see [wang2022query] + +Up: [provenance] for [panda] diff --git a/query b/query @@ -12,3 +12,7 @@ - [minimal_witness] Up: [database_theory] + +Aliases: queries + +See also: [knowledge_compilation_query] diff --git a/query_boolean b/query_boolean @@ -0,0 +1,11 @@ +# Boolean query + +A [query] whose [query_answer] is a [Boolean]: either the query holds or it does not. + +For [queries] with [free_variables] that are [first_order], the [computational_complexity] of computing [query_answers] is often [PTIME]-equivalent to the Boolean queries obtained by considering each of the polynomially many possible answers and creating a Boolean query by insantianing these [variables] to [constant] + +Up: [query] + +Aliases: boolean query + +See also: [free_variable] diff --git a/query_full b/query_full @@ -0,0 +1,9 @@ +# Full query + +A [query] in [first_order_logic] with no [projection], i.e., no [existential_quantification]: every [variable] used in the [query] is an [output_variable] + +Makes sense in particular for [CQs]: [conjunctive_query_full] + +Up: [query] + +Aliases: full query, full queries diff --git a/query_language b/query_language @@ -39,3 +39,5 @@ Up: [database_theory] See also: [query_rewriting] + +Aliases: query class, query classes, query languages diff --git a/query_recursive b/query_recursive @@ -0,0 +1,10 @@ +# Query recursive + +- [regular_path_query] +- [datalog] + - with [negation] + - with [aggregation] + +Up: [query_language] + +Aliases: recursive query, recursive queries diff --git a/ramsey_theorem b/ramsey_theorem @@ -10,6 +10,8 @@ Generalizations: - [hypergraphs] - https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Hypergraphs -Can also be useful in [formal_language_theory] +Can also be useful in [formal_language_theory]: [ramsey_formal_languages] Up: [mathematics] + +Aliases: Ramsey's theorem diff --git a/representation b/representation @@ -0,0 +1,8 @@ +# Representation + +- of [boolean_function] + - [boolean_formula] + - [boolean_circuit] + - [pseudo_boolean_constraint] + +Up: [mathematics] diff --git a/satisfiability_weighted b/satisfiability_weighted @@ -1,7 +1,6 @@ # Weighted satisfiability -creignou2012satisfiability: given a [formula_boolean] phi and integer k, decide -if phi has a [satisfying_assignment] of [hamming_weight] exactly k +[creignou2012satisfiability]: given a [Boolean_formula] phi and [integer] k, decide if phi has a [satisfying_assignment] of [hamming_weight] exactly k - [satisfiability_weighted_monotone_cnf] diff --git a/semantic_treewidth b/semantic_treewidth @@ -0,0 +1,17 @@ +# Semantic treewidth + +The semantic treewidth of a [query] Q in a certain [query_class] C is the smallest value k such that Q is [query_equivalent] to a [query] in C having [treewidth] k + +Can be studied for [query_classes] such as [CQs] or for [UC2RPQs] + +Relevant papers: + +- [figueira2023approximation], [journal_version] [figueira2024semantic]: + - deciding whether a [UC2RPQ] is [query_equivalent] to a [query] of [treewidth] at most k is in [2EXPSPACE] + - also studies how to do [query_approximation] of [UC2RPQs] with [queries] of small [treewidth] +- better algorithm for evaluation ([fixed_parameter_tractable], singly exponential): [feier2024evaluating] + - cites [figueira2023approximation] + +See also: [semantic_acyclicity] + +Up: [database_theory] diff --git a/spanning_tree b/spanning_tree @@ -6,3 +6,5 @@ See also: [steiner_tree] Up: [tree] + +Aliases: spanning trees diff --git a/statistics b/statistics @@ -0,0 +1,6 @@ +# Statistics + +- [average] +- [median] + +Up: [mathematics_fields] diff --git a/subgraph b/subgraph @@ -0,0 +1,7 @@ +# Subgraph + +A [graph] obtained from another [graph] by keeping the same [vertices] and a [subset] of the [edges] + +Up: [graph] + +Aliases: subgraphs diff --git a/submodular_approximation b/submodular_approximation @@ -0,0 +1,5 @@ +# Submodular approximation + +[hochbaum2017submodular] + +Up: [submodular_optimization], [approximation] diff --git a/submodular_function b/submodular_function @@ -0,0 +1,9 @@ +# Submodular function + +- on [sets]: [submodular_set_function] +- the [domain] may be different + +[zivny2009expressive]: [submodular_function_locally_defined], i.e., a [sum] of [functions] of bounded [arity] + - related to [pseudo_boolean_optimization] + +Up: [function] diff --git a/submodular_optimization b/submodular_optimization @@ -4,5 +4,6 @@ https://en.wikipedia.org/wiki/Submodular_set_function#Optimization_problems - [submodular_minimization] - [submodular_maximization] +- [submodular_approximation] -Up: [optimization] +Up: [optimization], [submodular_function] diff --git a/submodular_set_function b/submodular_set_function @@ -9,4 +9,4 @@ Implies being [subadditive], converse is not true in general See also: [submodular_optimization], [concave_function] -Up: [function] +Up: [submodular_function] diff --git a/theorem b/theorem @@ -37,3 +37,5 @@ A [result] in [mathematics], recognized as challenging to prove Up: [mathematics] See also: [automated_theorem_proving], [theoremkb] + +Aliases: theorems diff --git a/threshold b/threshold @@ -0,0 +1,7 @@ +# Threshold + +- [positive_threshold_function] +- [pqe_threshold] +- [locally_threshold_testable_language] + +Up: [mathematics] diff --git a/tree_even b/tree_even @@ -0,0 +1,13 @@ +# Tree even + +A [tree] where the length of the unique [path] connecting any two [leaves] is [even] + +[hanaka2024complexity] studies the problem of finding [spanning_trees] that are even. +- [NP_hard] on general [undirected_graphs] +- [PTIME] on [bipartite_graphs] + +Up: [tree] + +Aliases: even tree, even trees + +See also: [tree_odd] diff --git a/tree_odd b/tree_odd @@ -0,0 +1,11 @@ +# Tree odd + +A [tree] where the length of the unique [path] connecting any two [leaves] is [odd] + +[hanaka2024complexity] remarks it is equivalent to requiring that the tree is a [path] + +Up: [tree] + +See also: [tree_even] + +Aliases: odd tree, odd trees diff --git a/triangle_free_graph b/triangle_free_graph @@ -6,4 +6,6 @@ They are known to have unbounded [chromatic_number] [computational_problem] of recognizing them: see [triangle_detection] -Up: [triangle], [graph] +Up: [triangle], [graph], [graph_h_free] + +Aliases: triangle-free graph, triangle free graph, triangle-free graphs, triangle free graphs diff --git a/tseytin_transformation b/tseytin_transformation @@ -0,0 +1,7 @@ +# Tseytin transformation + +https://en.wikipedia.org/wiki/Tseytin_transformation + +Transform a [Boolean_circuit] into [equisatisfiable] [CNF], by adding some additional [variables] + +Up: [circuit] diff --git a/uc2rpq b/uc2rpq @@ -1,9 +1,12 @@ # UC2RPQ -union of [c2rpq] - -- [feier2024evaluating]: article on [treewidth] +[query_union] of [C2RPQs] +Studied for such [queries]: - [semantic_acyclicity] + - [figueira2024semantic] + - [feier2024evaluating]: article on [treewidth] and Up: [graph_query_languages], [c2rpq], [union_of_conjunctive_queries] + +Aliases: UC2RPQs diff --git a/uncertain_data b/uncertain_data @@ -0,0 +1,6 @@ +# Uncertain data + +- [inconsistency] +- [certain_answers] + +Up: [probabilistic_databases]