Property testing lower bounds via a generalization of randomized parity decision trees
From MaRDI portal
Publication:1999996
DOI10.1007/s00224-018-9880-3zbMath1425.68452OpenAlexW2882983798MaRDI QIDQ1999996
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
linear codesaffine subspacescommunication complexityproperty testinglinear-access algorithmsparity decision trees
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