Tight lower bounds for testing linear isomorphism

DOI10.1007/978-3-642-40328-6_39zbMATH Open1405.68128OpenAlexW157152022MaRDI QIDQ2851886FDOQ2851886

Authors: Elena Grigorescu, Karl Wimmer, Ning Xie 

Publication date: 4 October 2013

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-40328-6_39

Recommendations

• Property testing bounds for linear and quadratic functions via parity decision trees
• Nearly tight bounds for testing function isomorphism
• Nearly tight bounds for testing function isomorphism
• Testing linear-invariant function isomorphism
• Tight bounds for testing \(k\)-linearity

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Boolean functions (06E30)

Cited In (8)

• A unified framework for testing linear-invariant properties
• Testing linear-invariant function isomorphism
• Property testing lower bounds via a generalization of randomized parity decision trees
• Tight bounds and conjectures for the isolation lemma
• Property testing bounds for linear and quadratic functions via parity decision trees
• Tight bounds for testing \(k\)-linearity
• Lower bounds for linear degeneracy testing
• Polynomial-time algorithms for quadratic isomorphism of polynomials: the regular case

This page was built for publication: Tight lower bounds for testing linear isomorphism

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