Nearly tight bounds for testing function isomorphism

DOI10.1137/110832677MaRDI QIDQ2840979zbMATH OpenOpenAlexFDO

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

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

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)

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

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)