Partially Symmetric Functions Are Efficiently Isomorphism Testable

DOI10.1137/140971877zbMath1314.05211arXiv1112.5741OpenAlexW2179516467MaRDI QIDQ5252692

Yuichi Yoshida, Amit Weinstein, Eric Blais

Publication date: 2 June 2015

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

Full work available at URL: https://arxiv.org/abs/1112.5741

zbMATH Keywords

Boolean functionsproperty testingpartial symmetry

Mathematics Subject Classification ID

Symmetric functions and generalizations (05E05) Boolean functions (06E30) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (7)

On Active and Passive Testing ⋮ Revisiting Deutsch-Jozsa algorithm ⋮ Testing properties of functions on finite groups ⋮ A characterization of constant‐sample testable properties ⋮ Partially Symmetric Functions Are Efficiently Isomorphism Testable ⋮ Unnamed Item ⋮ Testing Boolean Functions Properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing juntas
• The complete intersection theorem for systems of finite sets
• Property testing lower bounds via communication complexity
• Property testing. Current research and surveys
• The exact bound in the Erdős-Ko-Rado theorem
• On the hardness of approximating minimum vertex cover
• On the measure of intersecting families, uniqueness and stability
• Local correction with constant error rate
• Exact Kolmogorov and total variation distances between some familiar discrete distributions
• Nearly Tight Bounds for Testing Function Isomorphism
• Efficient Sample Extractors for Juntas with Applications
• Property testing and its connection to learning and approximation
• Tight Bounds for Testing k-Linearity
• Sublinear Time Algorithms
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Boolean Functions, Invariance Groups, and Parallel Complexity
• The difficulty of testing for isomorphism against a graph that is given in advance
• Testing Boolean Function Isomorphism
• On Testing Computability by Small Width OBDDs
• Variable orderings and the size of OBDDs for random partially symmetric Boolean functions
• Robust Characterizations of Polynomials with Applications to Program Testing
• A unified framework for testing linear‐invariant properties
• Testing juntas nearly optimally
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• lgorithmic and Analysis Techniques in Property Testing
• Partially Symmetric Functions Are Efficiently Isomorphism Testable
• Universal Logic Modules and Their Applications
• On Detecting Total or Partial Symmetry of Switching Functions
• Algebraic Properties of Symmetric and Partially Symmetric Boolean Functions

This page was built for publication: Partially Symmetric Functions Are Efficiently Isomorphism Testable