Property testing lower bounds via communication complexity
From MaRDI portal
Publication:693004
DOI10.1007/s00037-012-0040-xzbMath1253.68142OpenAlexW2100732817MaRDI QIDQ693004
Kevin Matulef, Joshua Brody, Eric Blais
Publication date: 7 December 2012
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-012-0040-x
Related Items (36)
An adaptivity hierarchy theorem for property testing ⋮ Parameterized property testing of functions ⋮ An optimal tester for \(k\)-linear ⋮ On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Almost optimal proper learning and testing polynomials ⋮ Improved algorithm for permutation testing ⋮ An optimal tester for \(k\)-Linear ⋮ On Active and Passive Testing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Erasure-Resilient Property Testing ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Monotonicity testing and shortest-path routing on the cube ⋮ Zero-Knowledge Proofs of Proximity ⋮ Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces ⋮ One-Sided Error Communication Complexity of Gap Hamming Distance. ⋮ The NOF multiparty communication complexity of composed functions ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Adaptive Lower Bound for Testing Monotonicity on the Line ⋮ Lower Bounds for Testing Computability by Small Width OBDDs ⋮ Non-interactive proofs of proximity ⋮ Efficient Sample Extractors for Juntas with Applications ⋮ Property testing lower bounds via a generalization of randomized parity decision trees ⋮ Property testing lower bounds via communication complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube ⋮ On Approximating the Number of Relevant Variables in a Function ⋮ Querying a Matrix Through Matrix-Vector Products. ⋮ Testing computability by width-two OBDDs ⋮ Unnamed Item ⋮ A Polynomial Lower Bound for Testing Monotonicity ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Partially Symmetric Functions Are Efficiently Isomorphism Testable ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An information statistics approach to data stream and communication complexity
- Testing juntas
- Property testing lower bounds via communication complexity
- Property testing. Current research and surveys
- Self-testing/correcting with applications to numerical problems
- Spot-checkers
- A lower bound for testing juntas
- Lower Bounds for Testing Computability by Small Width OBDDs
- Efficient Sample Extractors for Juntas with Applications
- Property testing and its connection to learning and approximation
- Tight Bounds for Testing k-Linearity
- Improved Bounds for Testing Juntas
- Monotonicity testing over general poset domains
- Testing Boolean Function Isomorphism
- Monotonicity Testing and Shortest-Path Routing on the Cube
- Better Gap-Hamming Lower Bounds via Better Round Elimination
- On Testing Computability by Small Width OBDDs
- Testing Computability by Width Two OBDDs
- The Probabilistic Communication Complexity of Set Intersection
- On Testing Convexity and Submodularity
- Testing Basic Boolean Formulae
- Robust Characterizations of Polynomials with Applications to Program Testing
- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
- Transitive-Closure Spanners
- Testing juntas nearly optimally
- lgorithmic and Analysis Techniques in Property Testing
- On Approximating the Number of Relevant Variables in a Function
- Testing monotonicity
This page was built for publication: Property testing lower bounds via communication complexity
