Efficient computation of approximate isomorphisms between Boolean functions

DOI10.1016/J.IPL.2015.11.009MaRDI QIDQ903194zbMATH OpenOpenAlexFDO

Authors Hans Ulrich Simon

Publication date 5 January 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2015.11.009

zbMATH Keywords

analysis of algorithmsrandomized algorithmsapproximation algorithmsisomorphism problemBoolean functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Boolean functions (06E30)

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
• Hypergraph isomorphism and structural equivalence of Boolean functions
• On the computational complexity of some classical equivalence relations on boolean functions

Cites work

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Isomorphism testing of Boolean functions computable by constant-depth circuits
• Probability Inequalities for Sums of Bounded Random Variables
• The Formula Isomorphism Problem

Cited in

(2)

• Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits
• Isomorphism testing of Boolean functions computable by constant-depth circuits

This page was built for publication: Efficient computation of approximate isomorphisms between Boolean functions

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