Testing juntas

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

Dana Ron, Alex Samorodnitsky, Shmuel Safra, Eldar Fischer, 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 functions; Discrete Fourier Analysis; Juntas; Property testing

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

60G50: Sums of independent random variables; random walks

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W20: Randomized algorithms

Related Items

Testing Juntas: A Brief Survey, Testing by Implicit Learning: A Brief Survey, Invariance in Property Testing, Testing (Subclasses of) Halfspaces, Distribution-free connectivity testing for sparse graphs, Learning functions of \(k\) relevant variables

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