Testing Boolean function isomorphism

DOI10.1007/978-3-642-15369-3_30MaRDI QIDQ3588423zbMATH OpenOpenAlexFDO

Authors Noga Alon, Eric Blais

Publication date 10 September 2010

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15369-3_30

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)

Recommendations

• Nearly tight bounds for testing function isomorphism
• Nearly tight bounds for testing function isomorphism
• Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits
• Isomorphism testing of Boolean functions computable by constant-depth circuits
• Testing linear-invariant function isomorphism

Cited in

(14)

• Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits
• Testing linear-invariant function isomorphism
• Local correction with constant error rate
• On the isomorphism problem for decision trees and decision lists
• Local correction of juntas
• Nearly tight bounds for testing function isomorphism
• Property testing lower bounds via communication complexity
• Isomorphism testing of Boolean functions computable by constant-depth circuits
• Efficient computation of approximate isomorphisms between Boolean functions
• Checking Reversibility of Boolean Functions
• A characterization of testable hypergraph properties
• Nearly tight bounds for testing function isomorphism
• Hypergraph isomorphism and structural equivalence of Boolean functions
• Partially symmetric functions are efficiently isomorphism testable

This page was built for publication: Testing Boolean function isomorphism

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