Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits

DOI10.1007/978-3-642-28332-1_8MaRDI QIDQ2890182zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Yadu Vasudev

Publication date 8 June 2012

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-28332-1_8

zbMATH Keywords

Boolean functionsconstant-depth circuitsisomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Fault detection; testing in circuits and networks (94C12)

Recommendations

• Isomorphism testing of Boolean functions computable by constant-depth circuits
• STACS 2004
• Efficient computation of approximate isomorphisms between Boolean functions
• scientific article; zbMATH DE number 3878850
• Nearly tight bounds for testing function isomorphism
• Nearly tight bounds for testing function isomorphism
• On a hierarchy of Boolean functions hard to compute in constant depth
• On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions
• Testing Boolean function isomorphism
• The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis

Cited in

(6)

• On the isomorphism problem for decision trees and decision lists
• Hypergraph isomorphism and structural equivalence of Boolean functions
• On the isomorphism problem for decision trees and decision lists
• Testing Boolean function isomorphism
• Isomorphism testing of Boolean functions computable by constant-depth circuits
• Efficient computation of approximate isomorphisms between Boolean functions

This page was built for publication: Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits

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