Nearly tight bounds for testing function isomorphism

DOI10.1137/110832677zbMATH Open1275.68072OpenAlexW2052003531MaRDI QIDQ2840979FDOQ2840979

Authors Noga Alon, Eric Blais, Sourav Chakraborty, David García-Soriano, Arie Matsliah

Publication date 24 July 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/110832677

zbMATH Keywords

Boolean functionsisomorphismproperty testing

Mathematics Subject Classification ID

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

Recommendations

• Nearly tight bounds for testing function isomorphism
• Testing Boolean function isomorphism
• Improved Bounds for Testing Juntas
• Partially symmetric functions are efficiently isomorphism testable
• Testing juntas nearly optimally

Cited in

(15)

• Tolerant junta testing and the connection to submodular optimization and function isomorphism
• Nearly tight bounds for testing function isomorphism
• Tight lower bounds for testing linear isomorphism
• Local correction with constant error rate
• Attribute estimation and testing quasi-symmetry
• Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits
• Testing Boolean functions properties
• Efficient sample extractors for juntas with applications
• Property testing bounds for linear and quadratic functions via parity decision trees
• Tolerant junta testing and the connection to submodular optimization and function isomorphism
• The query complexity of graph isomorphism: bypassing distribution testing lower bounds
• Testing linear-invariant function isomorphism
• Partially symmetric functions are efficiently isomorphism testable
• Testing Boolean function isomorphism
• Isomorphism testing of Boolean functions computable by constant-depth circuits

This page was built for publication: Nearly tight bounds for testing function isomorphism

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