On approximating the number of relevant variables in a function

DOI10.1145/2493246.2493250MaRDI QIDQ5892190zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• On approximating the number of relevant variables in a function
• Learning functions of \(k\) relevant variables
• Exact learning when irrelevant variables abound
• Testing juntas nearly optimally
• On learning monotone Boolean functions with irrelevant variables

Cited in

(1)

• On approximating the number of relevant variables in a function

This page was built for publication: On approximating the number of relevant variables in a function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5892190)