Testing juntas
DOI10.1016/J.JCSS.2003.11.004zbMATH Open1076.68112OpenAlexW2914377170MaRDI QIDQ598252FDOQ598252
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
Recommendations
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)
Cites Work
- Shuffling Cards and Stopping Times
- Proof verification and the hardness of approximation problems
- Property testing and its connection to learning and approximation
- Learning juntas
- Probabilistic checking of proofs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Monotonicity testing over general poset domains
- Robust Characterizations of Polynomials with Applications to Program Testing
- Title not available (Why is that?)
- Testing monotonicity
- Learning in the presence of finitely or infinitely many irrelevant attributes
- Title not available (Why is that?)
- The importance of being biased
- Testing Basic Boolean Formulae
- PCP characterizations of NP: towards a polynomially-small error-probability
- Title not available (Why is that?)
Cited In (38)
- A unified framework for testing linear-invariant properties
- Almost optimal distribution-free junta testing
- Testing juntas nearly optimally
- Title not available (Why is that?)
- A local decision test for sparse polynomials
- The complexity of computing (almost) orthogonal matrices with \(\varepsilon\)-copies of the Fourier transform
- Application of hypergraph Hoffman's bound to intersecting families
- Testing by implicit learning: a brief survey
- An orthogonal basis for functions over a slice of the Boolean hypercube
- Attribute estimation and testing quasi-symmetry
- 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
- \(K_4\)-intersecting families of graphs
- Local correction of juntas
- Boolean degree 1 functions on some classical association schemes
- Testing (Subclasses of) Halfspaces
- Efficient sample extractors for juntas with applications
- On approximating the number of relevant variables in a function
- Lower Bounds for Testing Computability by Small Width OBDDs
- 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)
