Property testing lower bounds via a generalization of randomized parity decision trees

DOI10.1007/s00224-018-9880-3zbMath1425.68452OpenAlexW2882983798MaRDI QIDQ1999996

Roei Tell

Publication date: 27 June 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-018-9880-3

zbMATH Keywords

linear codesaffine subspacescommunication complexityproperty testinglinear-access algorithmsparity decision trees

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Property testing lower bounds via communication complexity
• On the parity complexity measures of Boolean functions
• Self-testing/correcting with applications to numerical problems
• Linear codes and character sums
• On the structure of Boolean functions with small spectral norm
• The Complexity of DNF of Parities
• An Introduction to Randomness Extractors
• Tight Bounds for Testing k-Linearity
• On Testing Computability by Small Width OBDDs
• Communication Complexity
• Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees
• Introduction to Property Testing
• Every locally characterized affine-invariant property is testable