# Property Testing Lower Bounds & Communication Complexity
> Learn about monotonicity testing on the hypercube, the BLR linearity test, and proving query complexity lower bounds using communication complexity reductions.

Tags: property-testing, theoretical-computer-science, communication-complexity, monotonicity-testing, query-complexity, algorithms
## Slide 1: Lower Bounds in Property Testing
* Lecture topics: From Linearity to Communication Complexity.
* Focus: New Property Testing constructions for monotonicity.

## Slide 2-5: Property Testing Framework
* Model: Black-box access to function f: D → R with a query complexity goal.
* Definitions: f is ̕-far from Property P if ≥ ̕|D| entries must change to make f ∈ P.
* Tester Goal: Accept if f ∈ P; Reject with high probability (2/3) if f is far from P.

## Slide 6-9: Monotonicity Testing on the Hypercube
* Upper Bound: O(n/̕) query complexity for Boolean range using the Edge Tester.
* Edge Tester: Pick a random edge (x,y); reject if f(x)=1 and f(y)=0.
* Analysis: Uses the Edge Isoperimetric Inequality: violated edges ≥ ̕ ∙ n ∙ 2^{n-1}.

## Slide 10-15: Monotonicity Lower Bounds
* Theorem: For large ranges, monotonicity testers require ̐(n) queries.
* Strategy: Reduction from Unique-Disjointness (UDISJ).
* The Gadget: h_{A,B}(S) = 2|S| + (-1)^{|S ∩ A|} + (-1)^{|S ∩ B|}.
* If A ∩ B = ∅, f is monotone; if |A ∩ B| = 1, f is 1/8-far from monotone.

## Slide 16-20: The Reduction Protocol
* Alice & Bob simulate a tester Q by communicating bits to compute the parity terms of h_{A,B}(S).
* Result: Total Communication = 2 ∙ Query Complexity(Q).
* Conclusion: Since UDISJ requires ̐(n) bits, Query Complexity q(n) must be ̐(n).
---
This presentation was created with [Bobr AI](https://bobr.ai) — an AI presentation generator.