Tight lower bounds for testing linear isomorphism

DOI10.1007/978-3-642-40328-6_39MaRDI QIDQ2851886zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(9)

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

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)