Nearly Tight Bounds for Testing Function Isomorphism

DOI10.1137/110832677zbMath1275.68072OpenAlexW2052003531MaRDI QIDQ2840979

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

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)

Related Items (4)

Efficient Sample Extractors for Juntas with Applications ⋮ Partially Symmetric Functions Are Efficiently Isomorphism Testable ⋮ Local correction with constant error rate ⋮ Testing Boolean Functions Properties

This page was built for publication: Nearly Tight Bounds for Testing Function Isomorphism