A duality between Boolean functions

DOI10.1017/S1474748010000083zbMATH Open1192.68301OpenAlexW2098688519MaRDI QIDQ3569370FDOQ3569370

Authors: Bruno Poizat 

Publication date: 18 June 2010

Published in: Journal of the Institute of Mathematics of Jussieu (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s1474748010000083

Recommendations

• scientific article; zbMATH DE number 4108153
• Dualities in the class of extended Boolean functions
• Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
• Complexity of identification and dualization of positive Boolean functions
• Monotone Boolean dualization is in co-NP\([\log^{2}n]\).

zbMATH Keywords

parallelizationparsimonious reductioncomplexity of computationsvaliantarithmetic circuits and termsmalod

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• The complexity of computing the permanent
• Characterizing Valiant's algebraic complexity classes
• Completeness and reduction in algebraic complexity theory
• Restructuring of Arithmetic Expressions For Parallel Evaluation
• A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
• On the Time Necessary to Compute Switching Functions

Cited In (4)

• Dualities in the class of extended Boolean functions
• Boolean functions with MacWilliams duality
• Alternative definitions of Boolean functions and relations
• Dualization of regular Boolean functions

This page was built for publication: A duality between Boolean functions

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