Isomorphism testing of Boolean functions computable by constant-depth circuits

DOI10.1016/J.IC.2014.08.003MaRDI QIDQ476155zbMATHOpenAlexFDO

Authors Vikraman Arvind, Yadu Vasudev

Publication date 28 November 2014

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2014.08.003

zbMATH Keywords

Boolean functionsisomorphismconstant-depth circuits

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
• Efficient computation of approximate isomorphisms between Boolean functions
• Testing Boolean function isomorphism
• Hypergraph isomorphism and structural equivalence of Boolean functions
• Nearly tight bounds for testing function isomorphism

Cites work

• Constant depth circuits, Fourier transform, and learnability
• Hypergraph isomorphism and structural equivalence of Boolean functions
• Isomorphism testing of read-once functions and polynomials
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Nearly tight bounds for testing function isomorphism
• Parity, circuits, and the polynomial-time hierarchy
• Testing Boolean function isomorphism
• The Formula Isomorphism Problem

Cited in

(6)

• Hypergraph isomorphism and structural equivalence of Boolean functions
• Efficient computation of approximate isomorphisms between Boolean functions
• On the isomorphism problem for decision trees and decision lists
• Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits
• On the isomorphism problem for decision trees and decision lists
• Testing Boolean function isomorphism

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 Q476155)