Testing juntas
From MaRDI portal
Publication:598252
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
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
