2-Xor revisited: satisfiability and probabilities of functions

DOI10.1007/S00453-016-0119-XzbMATH Open1352.68193arXiv1511.07813OpenAlexW2261120410MaRDI QIDQ727973FDOQ727973

Authors: Bernhard Gittenberger, Markus Kuba, Elie de Panafieu, Danièle Gardy 

Publication date: 21 December 2016

Published in: Algorithmica (Search for Journal in Brave)

Abstract: The problem 2-Xor-Sat asks for the probability that a random expression, built as a conjunction of clauses $xoplusy$, is satisfiable. We revisit this classical problem by giving an alternative, explicit expression of this probability. We then consider a refinement of it, namely the probability that a random expression computes a specific Boolean function. The answers to both problems involve a description of 2-Xor expressions as multigraphs and use classical methods of analytic combinatorics by expressing probabilities through coefficients of generating functions.

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

Recommendations

• Probabilities of 2-Xor Functions
• Random 2 XORSAT phase transition
• Random 2-XORSAT at the Satisfiability Threshold
• Satisfiability threshold for random XOR-CNF formulas
• Limit Theorems for Random MAX-2-XORSAT

zbMATH Keywords

asymptoticssatisfiability2-Xor expressionsmultigraph enumerationprobability of Boolean functions

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Random 2-XORSAT at the Satisfiability Threshold
• Crooked indifferentiability of enveloped XOR revisited
• Probabilities of 2-Xor Functions
• Title not available (Why is that?)
• Random 2 XORSAT phase transition
• A two-dimensional approach to flexibility degree of XOR numbers with application to group decision making
• Enumerating lambda terms by weighted length of their de Bruijn representation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q727973)