Property testing lower bounds via a generalization of randomized parity decision trees
type: Item
instance of: scholarly article
title: Property testing lower bounds via a generalization of randomized parity decision trees
zbMATH Open document ID: 1425.68452
author: Roei Tell
published in: Theory of Computing Systems
publication date: 2019-06-27T00:00:00Z
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 94B05
zbMATH DE Number: 7074489
zbMATH Keywords: property testing
zbMATH Keywords: communication complexity
zbMATH Keywords: parity decision trees
zbMATH Keywords: linear-access algorithms
zbMATH Keywords: affine subspaces
zbMATH Keywords: linear codes
MaRDI profile type: Publication
full work available at URL: s00224-018-9880-3
OpenAlex ID: W2882983798
cites work: Every locally characterized affine-invariant property is testable
cites work: Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees
cites work: Property testing lower bounds via communication complexity
cites work: Tight Bounds for Testing k-Linearity
cites work: Self-testing/correcting with applications to numerical problems
cites work: Q5414625
cites work: The complexity of DNF of parities
cites work: On Testing Computability by Small Width OBDDs
cites work: Introduction to Property Testing
cites work: Q3002788
cites work: Communication Complexity
cites work: Linear codes and character sums
cites work: Q4038696
cites work: An Introduction to Randomness Extractors
cites work: On the structure of Boolean functions with small spectral norm
cites work: On the parity complexity measures of Boolean functions
DOI: 10.1007/S00224-018-9880-3
description: scientific article; zbMATH DE number 7074489