Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees
From MaRDI portal
Publication:4981152
DOI10.1007/978-3-319-06686-8_8zbMath1408.68145MaRDI QIDQ4981152
Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni
Publication date: 24 June 2014
Published in: Computer Science - Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-06686-8_8
68W40: Analysis of algorithms
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W20: Randomized algorithms
Related Items
An adaptivity hierarchy theorem for property testing, Property testing lower bounds via a generalization of randomized parity decision trees