Almost Optimal Testers for Concise Representations.

DOI10.4230/LIPICS.APPROX/RANDOM.2020.5MaRDI QIDQ6084348zbMATH OpenOpenAlexFDO

Authors Nader H. Bshouty

Publication date 31 October 2023

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

zbMATH Keywords

Boolean functionJuntaproperty testing

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Abstract: We give improved and almost optimal testers for several classes of Boolean functions on $n$ inputs that have concise representation in the uniform and distribution-free model. Classes, such as $k$-junta, $k$-linear functions, $s$-term DNF, $s$-term monotone DNF, $r$-DNF, decision list, $r$-decision list, size-$s$ decision tree, size-$s$ Boolean formula, size-$s$ branching programs, $s$-sparse polynomials over the binary field and function with Fourier degree at most $d$. The method can be extended to several other classes of functions over any domain that can be approximated by functions that have a small number of relevant variables.

Cites work

• A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
• A polynomial lower bound for testing monotonicity
• A theory of the learnable
• Adaptive versus nonadaptive attribute-efficient learning
• Algorithmic and analysis techniques in property testing
• An O(n) queries adaptive tester for unateness
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
• Distribution-Free Property-Testing
• Distribution-free testing for monomials with a sublinear number of queries
• Distribution-free testing lower bound for basic Boolean functions
• Efficient sample extractors for juntas with applications
• Efficiently testing sparse \(\text{GF}(2)\) polynomials
• scientific article; zbMATH DE number 1453048 (Why is no real title available?)
• Introduction to Property Testing
• Learning functions of \(k\) relevant variables
• Learning regular sets from queries and counterexamples
• Optimal testing of Reed-Muller codes
• Property testing and its connection to learning and approximation
• Property testing. Current research and surveys
• Robust Characterizations of Polynomials with Applications to Program Testing
• Selection of relevant features and examples in machine learning
• Self-testing/correcting with applications to numerical problems
• Testing Basic Boolean Formulae
• Testing Fourier dimensionality and sparsity
• Testing Halfspaces
• Testing juntas nearly optimally
• Testing monotonicity
• Testing Reed–Muller Codes
• Testing ±1-weight halfspace
• Tight bounds for testing k-linearity
• Tight bounds for the distribution-free testing of monotone conjunctions

Cited in

(5)

• Input-Thrifty Extrema Testing
• Optimal unateness testers for real-valued functions: Adaptivity helps
• On one-sided testing affine subspaces
• On one-sided testing affine subspaces
• Relative-error testing of conjunctions and decision lists

This page was built for publication: Almost Optimal Testers for Concise Representations.

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