Pages that link to "Item:Q693004"
From MaRDI portal
The following pages link to Property testing lower bounds via communication complexity (Q693004):
Displayed 36 items.
- Monotonicity testing and shortest-path routing on the cube (Q452855) (← links)
- The NOF multiparty communication complexity of composed functions (Q496305) (← links)
- Property testing lower bounds via communication complexity (Q693004) (← links)
- Testing computability by width-two OBDDs (Q764366) (← links)
- An adaptivity hierarchy theorem for property testing (Q1630385) (← links)
- Sublinear-time algorithms for counting star subgraphs via edge sampling (Q1709591) (← links)
- Non-interactive proofs of proximity (Q1745962) (← links)
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity (Q1983326) (← links)
- Property testing lower bounds via a generalization of randomized parity decision trees (Q1999996) (← links)
- An optimal tester for \(k\)-linear (Q2154097) (← links)
- An optimal tester for \(k\)-Linear (Q2690878) (← links)
- An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube (Q2805510) (← links)
- Lower Bounds for Testing Computability by Small Width OBDDs (Q3010413) (← links)
- Efficient Sample Extractors for Juntas with Applications (Q3012831) (← links)
- Erasure-Resilient Property Testing (Q4608990) (← links)
- Parameterized property testing of functions (Q4638061) (← links)
- (Q4638079) (← links)
- Zero-Knowledge Proofs of Proximity (Q4993282) (← links)
- A Polynomial Lower Bound for Testing Monotonicity (Q4994983) (← links)
- Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces (Q5002641) (← links)
- One-Sided Error Communication Complexity of Gap Hamming Distance. (Q5005103) (← links)
- (Q5009503) (← links)
- Adaptive Lower Bound for Testing Monotonicity on the Line (Q5009526) (← links)
- (Q5009536) (← links)
- (Q5090383) (← links)
- (Q5091207) (← links)
- Querying a Matrix Through Matrix-Vector Products. (Q5091255) (← links)
- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing (Q5098771) (← links)
- (Q5140837) (← links)
- Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity (Q5243170) (← links)
- Partially Symmetric Functions Are Efficiently Isomorphism Testable (Q5252692) (← links)
- On Active and Passive Testing (Q5364269) (← links)
- On Approximating the Number of Relevant Variables in a Function (Q5894227) (← links)
- Approximating the distance to monotonicity of Boolean functions (Q6074683) (← links)
- Almost optimal proper learning and testing polynomials (Q6109015) (← links)
- Improved algorithm for permutation testing (Q6138826) (← links)