Testing juntas

DOI10.1016/J.JCSS.2003.11.004MaRDI QIDQ598252zbMATH OpenOpenAlexFDO

Authors Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky

Publication date 6 August 2004

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2003.11.004

zbMATH Keywords

Boolean functionsDiscrete Fourier AnalysisJuntasProperty testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Sums of independent random variables; random walks (60G50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Testing juntas: a brief survey
• Testing juntas nearly optimally
• Adaptivity helps for testing juntas
• Just testing
• A lower bound for testing juntas

Cites work

• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 1418269 (Why is no real title available?)
• scientific article; zbMATH DE number 1453048 (Why is no real title available?)
• Learning in the presence of finitely or infinitely many irrelevant attributes
• Learning juntas
• Monotonicity testing over general poset domains
• PCP characterizations of NP: towards a polynomially-small error-probability
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Shuffling Cards and Stopping Times
• Testing Basic Boolean Formulae
• Testing monotonicity
• The importance of being biased

Cited in

(38)

• A unified framework for testing linear-invariant properties
• Almost optimal distribution-free junta testing
• Testing juntas nearly optimally
• A local decision test for sparse polynomials
• The complexity of computing (almost) orthogonal matrices with \(\varepsilon\)-copies of the Fourier transform
• scientific article; zbMATH DE number 7559095 (Why is no real title available?)
• Application of hypergraph Hoffman's bound to intersecting families
• Testing by implicit learning: a brief survey
• Attribute estimation and testing quasi-symmetry
• An orthogonal basis for functions over a slice of the Boolean hypercube
• A canonical form for testing Boolean function properties
• Local correction with constant error rate
• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• Local correction of juntas
• \(K_4\)-intersecting families of graphs
• Boolean degree 1 functions on some classical association schemes
• Efficient sample extractors for juntas with applications
• Testing (Subclasses of) Halfspaces
• Lower Bounds for Testing Computability by Small Width OBDDs
• On approximating the number of relevant variables in a function
• Boolean functions on \(S_n\) which are nearly linear
• Exponentially improved algorithms and lower bounds for testing signed majorities
• Property testing lower bounds via communication complexity
• An optimal tester for \(k\)-linear
• Testing Boolean functions properties
• Learning functions of \(k\) relevant variables
• Approximating the distance to monotonicity of Boolean functions
• Influence of a Set of Variables on a Boolean Function
• Testing submodularity and other properties of valuation functions
• Testing juntas: a brief survey
• On active and passive testing
• Invariance in property testing
• Efficiently testing sparse \(\text{GF}(2)\) polynomials
• Distribution-free connectivity testing for sparse graphs
• An optimal tester for \(k\)-Linear
• Testing computability by width-two OBDDs
• Reducing Testing Affine Spaces to Testing Linearity of Functions
• Partially symmetric functions are efficiently isomorphism testable

This page was built for publication: Testing juntas

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