Record link: 
http://hdl.handle.net/20.500.12708/28498
-
Title: 
Probabilities of 2-XOR functions
-
Citation: 
De Panafieu, E., Gardy, D., Gittenberger, B., & Kuba, M. (2014). Probabilities of 2-XOR functions. In A. Pardo & A. Viola (Eds.), LATIN 2014: Theoretical Informatics (pp. 454–465). Springer Verlag Berlin-Heidelberg. https://doi.org/10.1007/978-3-642-54423-1_40
-
Publisher DOI: 
10.1007/978-3-642-54423-1_40
-
Publication Type: 
Book Contribution - Edited Volume Contribution
en
Authors: 
De Panafieu, Elie 
Gardy, Daniele 
Gittenberger, Bernhard 
Kuba, Markus 
-
Organisational Unit: 
E104-05 - Forschungsbereich Kombinatorik und Algorithmen 
-
Published in: 
LATIN 2014: Theoretical Informatics 
-
ISBN: 
978-3-642-54423-1
-
DOI of the book: 
10.1007/978-3-642-54423-1
-
Date (published): 
2014
-
Number of Pages: 
12
-
Publisher: 
Springer-Verlag Berlin, Heidelberg
-
Abstract: 
The problem 2-Xor-Sat asks for the probability that a random expression, built as a conjunction of clauses x ⊕ y, is satisfiable. We consider here a refinement of this question, namely the probability that a random expression computes a specific Boolean function. The answer involves a description of 2-Xor expressions as multigraphs, and uses classical methods of analytic combinatorics.
en
Science Branch: 
Mathematik
-
Appears in Collections:
Book Contribution

Show full item record

Page view(s)

151
checked on Dec 1, 2023

Google ScholarTM

Check