Hypergraph isomorphism and structural equivalence of Boolean functions

DOI10.1145/301250.301427MaRDI QIDQ2819594zbMATH OpenOpenAlexFDO

Authors Eugene M. Luks

Publication date 29 September 2016

Published in Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/301250.301427

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Hypergraphs (05C65) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits
• Isomorphism testing of Boolean functions computable by constant-depth circuits
• Testing Boolean function isomorphism
• On the computational complexity of some classical equivalence relations on boolean functions
• On the isomorphism problem for decision trees and decision lists

Cited in

(21)

• Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
• Relative definability of boolean functions via hypergraphs
• Colored hypergraph isomorphism is fixed parameter tractable
• On the isomorphism problem for decision trees and decision lists
• Cooperation through social influence
• On isomorphism testing of groups with normal Hall subgroups
• Solution-Graphs of Boolean Formulas and Isomorphism
• On the isomorphism problem for decision trees and decision lists
• The parameterized complexity of geometric graph isomorphism
• Isomorphism testing of Boolean functions computable by constant-depth circuits
• Solution-Graphs of Boolean Formulas and Isomorphism1
• Algorithms for group isomorphism via group extensions and cohomology
• Foundations of Software Science and Computation Structures
• Topological Equivalence Classification of Balanced Linearly Separable Boolean Functions on n-Dimensional Hypercube
• Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice
• Hypergraph isomorphism for groups with restricted composition factors
• Computing equivalence classes among the edges of a graph with applications
• On p-group isomorphism: search-to-decision, counting-to-decision and nilpotency class reductions via tensors
• Complexity classes of equivalence problems revisited
• Efficient computation of approximate isomorphisms between Boolean functions
• Isomorphism and canonization of tournaments and hypertournaments

This page was built for publication: Hypergraph isomorphism and structural equivalence of Boolean functions

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