Almost optimal distribution-free junta testing

DOI10.4230/LIPIcs.CCC.2019.2OpenAlexW2966120871MaRDI QIDQ5091752

Nader H. Bshouty

Publication date: 27 July 2022

Full work available at URL: https://arxiv.org/abs/1901.00717

zbMATH Keywords

\(k\)-juntadistribution-free property testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

An optimal tester for \(k\)-linear

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Property testing. Current research and surveys
• Selection of relevant features and examples in machine learning
• Self-testing/correcting with applications to numerical problems
• Exact learning of juntas from membership queries
• Learning functions of \(k\) relevant variables
• A lower bound for testing juntas
• Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
• Testing Halfspaces
• Property testing and its connection to learning and approximation
• Tight Bounds for Testing k-Linearity
• Distribution-Free Property-Testing
• Improved Bounds for Testing Juntas
• Testing Reed–Muller Codes
• Monotonicity testing over general poset domains
• Testing ±1-weight halfspace
• Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions
• Distribution-free Junta Testing
• An ~O(n) Queries Adaptive Tester for Unateness
• Testing Basic Boolean Formulae
• Robust Characterizations of Polynomials with Applications to Program Testing
• Optimal Testing of Reed-Muller Codes
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• Testing juntas nearly optimally
• lgorithmic and Analysis Techniques in Property Testing
• A polynomial lower bound for testing monotonicity
• A o(n) monotonicity tester for boolean functions over the hypercube
• Testing Fourier Dimensionality and Sparsity
• Testing monotonicity

This page was built for publication: Almost optimal distribution-free junta testing