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.68145OpenAlexW115064344MaRDI 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
Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items
An adaptivity hierarchy theorem for property testing, Property testing lower bounds via a generalization of randomized parity decision trees