2-Xor revisited: satisfiability and probabilities of functions

DOI10.1007/S00453-016-0119-XzbMath1352.68193arXiv1511.07813OpenAlexW2261120410MaRDI QIDQ727973

Markus Kuba, Bernhard Gittenberger, Daniéle Gardy, Elie de Panafieu

Publication date: 21 December 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.07813

zbMATH Keywords

asymptoticssatisfiability2-Xor expressionsmultigraph enumerationprobability of Boolean functions

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Boolean functions (06E30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

Enumerating lambda terms by weighted length of their de Bruijn representation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilities of Boolean functions given by random implicational formulas
• Random 2 XORSAT phase transition
• Counting connected graphs asymptotically
• The first cycles in an evolving graph
• How frequently is a system of 2-linear Boolean equations solvable?
• Counting connected graphs inside-out
• Airy phenomena and analytic combinatorics of connected graphs
• Satisfiability threshold for random XOR-CNF formulas
• Associative and commutative tree representations for Boolean functions
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• The fraction of large random trees representing a given Boolean function in implicational logic
• The number of connected sparsely edged graphs. III. Asymptotic results
• Intuitionistic vs. Classical Tautologies, Quantitative Comparison
• Random Trees
• Classical and Intuitionistic Logic Are Asymptotically Identical
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• The number of connected sparsely edged graphs
• Some typical properties of large AND/OR Boolean formulas
• And/Or Trees Revisited
• Approximating the Satisfiability Threshold for Random k-XOR-formulas
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• The growing tree distribution on Boolean functions.
• The birth of the giant component
• Probabilities of 2-Xor Functions
• Analytic Description of the Phase Transition of Inhomogeneous Multigraphs
• The Boolean functions computed by random Boolean formulas or how to grow the right function

This page was built for publication: 2-Xor revisited: satisfiability and probabilities of functions