On Approximating the Number of Relevant Variables in a Function

DOI10.1145/2493246.2493250zbMath1322.68261OpenAlexW2162813991MaRDI QIDQ5892190

Dana Ron, Gilad Tsur

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2493246.2493250

zbMATH Keywords

property testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

On Approximating the Number of Relevant Variables in a Function