Testing juntas

DOI10.1016/j.jcss.2003.11.004zbMath1076.68112OpenAlexW2914377170MaRDI QIDQ598252

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

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) Sums of independent random variables; random walks (60G50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items

Learning functions of \(k\) relevant variables ⋮ Boolean degree 1 functions on some classical association schemes ⋮ An orthogonal basis for functions over a slice of the Boolean hypercube ⋮ Application of hypergraph Hoffman's bound to intersecting families ⋮ An optimal tester for \(k\)-linear ⋮ Reducing Testing Affine Spaces to Testing Linearity of Functions ⋮ \(K_4\)-intersecting families of graphs ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Influence of a Set of Variables on a Boolean Function ⋮ A local decision test for sparse polynomials ⋮ Boolean functions on $S_n$ which are nearly linear ⋮ An optimal tester for \(k\)-Linear ⋮ On Active and Passive Testing ⋮ Local correction of juntas ⋮ Efficiently testing sparse \(\text{GF}(2)\) polynomials ⋮ Distribution-free connectivity testing for sparse graphs ⋮ The complexity of computing (almost) orthogonal matrices with \(\varepsilon\)-copies of the Fourier transform ⋮ Lower Bounds for Testing Computability by Small Width OBDDs ⋮ Efficient Sample Extractors for Juntas with Applications ⋮ Property testing lower bounds via communication complexity ⋮ Testing Juntas: A Brief Survey ⋮ Testing by Implicit Learning: A Brief Survey ⋮ Invariance in Property Testing ⋮ Testing (Subclasses of) Halfspaces ⋮ Unnamed Item ⋮ On Approximating the Number of Relevant Variables in a Function ⋮ A Canonical Form for Testing Boolean Function Properties ⋮ Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity ⋮ A unified framework for testing linear‐invariant properties ⋮ Testing computability by width-two OBDDs ⋮ Partially Symmetric Functions Are Efficiently Isomorphism Testable ⋮ Unnamed Item ⋮ Local correction with constant error rate ⋮ Testing Boolean Functions Properties ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Learning in the presence of finitely or infinitely many irrelevant attributes
• PCP characterizations of NP
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• The importance of being biased
• Monotonicity testing over general poset domains
• Learning juntas
• Shuffling Cards and Stopping Times
• Probabilistic checking of proofs
• Testing Basic Boolean Formulae
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing monotonicity