### Lower Bounds for Testing Properties of Functions over Hypergrids

```Lower Bounds for Testing
Properties of Functions on
Hypergrids
Grigory Yaroslavtsev
http://grigory.us
⇒
⇒
Joint with:
Eric Blais (MIT)
Property Testing
[Goldreich, Goldwasser, Ron, Rubinfeld, Sudan]
Randomized algorithm
YES
⇒
Property tester
Accept with

probability ≥

YES
-close
No
⇒
Reject with

probability ≥

No
⇒
Accept with

probability ≥

⇒ Don’t care
⇒ Reject with
probability ≥
-close : ≤  fraction can be changed to become YES

Ultra-fast Approximate Decision Making
Property Testing
[Goldreich, Goldwasser, Ron, Rubinfeld, Sudan]
Property  = set of YES instances
Query complexity of testing :
•
() = Non-adaptive (all queries at once)
1
•  () = Queries in  rounds (

=

())
Communication Complexity [Yao’79]
Shared randomness
1 ()
2 (1 , )
(, ) =?
3 (2 , )
Alice:
…
(, )
Bob:
•   = min. communication (error 1/3)
•   = min. -round communication (error 1/3)
/2-disjointness ⇒ -linearity
[Blais, Brody,Matulef’11]
• -linear function: 0,1

→ {0,1}
⊕∈  = 1 ⊕ 2 ⊕ ⋯ ⊕
where || =
• /2-Disjointness: ,  ⊆ [],  =  =

2
(, ) = 1, iff  ∩  = 0.
: | ∩ | = 0?
Alice:  ⊆
= /
,
Bob:
⊆  ,  = /
/2-disjointness ⇒ -linearity
[Blais, Brody,Matulef’11]
=  ⊕
⊆  ,  = /
=⊕∈
⊆  ,  = /
=⊕∈
•  ∩  = ∅ ⇒  is -linear
•  ∩  ≠ ∅ ⇒  is (< )-linear, ½-far from -linear
• Test  for -linearity using shared randomness
• To evaluate   exchange  () and  () (2 bits)
•

−Disjointness
2
≤ 2 ⋅ ½ −Linearity
-Disjointness
•  −Disjointness = Θ  [Razborov, HastadWigderson]
•  −Disjointness = Θ( log )
[Folklore + Dasgupta, Kumar, Sivakumar’12; Buhrman, GarciaSoriano, Matsliah, De Wolf’12]
{
•  −Disjointness = Θ  ilog   ,
where   = log log … log  [Saglam, Tardos’13]
times
Ω  ilog   =  / −Linearity
•  −Disjointness =  + o()[Braverman,
Garg, Pankratov, Weinstein’13]
Property testing lower bounds via CC
• Monotonicity, Juntas, Low Fourier degree,
Small Decision Trees [Blais, Brody, Matulef’11]
• Small-width OBDD properties [Brody, Matulef,
Wu’11]
• Codes [Goldreich’13, Gur, Rothblum’13]
• Number of relevant variables [Ron, Tsur’13]
(Almost) all: Boolean functions over Boolean hypercube
Functions

, = monotone functions over
1 , = Ω  log

Previous for monotonicity on the line ( = 1):
• 1 , = Θ log  [Ergun, Kannan,
Kumar, Rubinfeld, Viswanathan’00]
•  , = Ω log  [Fischer’04]
Functions

• Proof ideas:
– Reduction from Augmented Index (widely used in
streaming, e.g [Jayram, Woodruff’11; Molinaro,
Woodruff, Y.’13])
– Fourier analysis over 0,1  basis of characters =>
Fourier analysis over   : basis of Walsh functions
• C  = : Any non-adaptive tester for
monotonicity of :  →  has complexity
Ω(min(log , log ))
Functions [] → ℝ [Blais, Raskhodnikova, Y.]
• Augmented Index: S; (,  ∩ [ − 1])
:  ∈ ?
1 ()
⊆
∈   ,  ∩ [ − 1]
• 1 Augmented Index = Ω(||) [Miltersen,
Nisan, Safra, Wigderson, 98]
Functions [] → ℝ [Blais, Raskhodnikova, Y.]
Walsh functions: For  ⊆ log  ,  : [] → {−1,1}:
= ∈ −1  ,
where  is the -th bit of .
=

=
…
=

Functions [] → ℝ [Blais, Raskhodnikova, Y.]
Step functions. For  ∈ log  :  :  →
= ⌈/2 ⌉
2 =

2
:

Functions [] → ℝ [Blais, Raskhodnikova, Y.]
• Augmented Index ⇒ Monotonicity Testing
= ∩[,…, ] + 2
=  ⊕ ∩[−1] + 2
⊆
∈   ,  ∩ [ − 1]
•  ∉  ⇒  is monotone
•  ∈  ⇒  is ¼ -far from monotone
• Only -th frequency matters: higher frequencies
are cancelled, lower don’t affect monotonicity
• Thus,  , = Ω log
Functions
⊆

∈    ,  ∩  − 1
⇒
⇒
, … ,  ⊆ [log ]
, , … , , ∗ , 0,0, … , 0
1 ,…, ∗ −1 , ∗ ∩ [∗ − 1]
Embed into ∗ -th coordiante using -dimensional
Walsh and step functions:
• Walsh functions:  (1 , … ,  ) =
• Step functions:  1 , … ,  =

=1  ( )

=1  ( )
Functions

, , … , , ∗ , 0,0, … , 0
1 ,…, ∗ −1 , ∗ ∩ [∗ − 1]
, … ,  ⊆ [log ]
, … ,  =
∗ ∩  ∗ ,…,log  ∗ ⊕

=  1 , . . ,  ⊕
+ 2∗ ∗ + 2

=∗ +1
+ 2  1 , . . ,
∗ −1
∗ −1
=1   + 2 =1 step

=∗ +1 0 ( )
• Walsh functions:  (1 , … ,  ) =
• Step functions:  1 , … ,  =

=1  ( )

=1  ( )
Functions

, , … , , ∗ , 0,0, … , 0
1 ,…, ∗ −1 , ∗ ∩ [∗ − 1]
, … ,  ⊆ [log ]
, … ,  =
1 , . . ,  ⊕
∗ −1
=1
+ 2∗ ∗ + 2

=∗ +1
• Only coordinate ∗ matters:
– Coordinates < ∗ cancelled by Bob’s Walsh terms
– Coordinates > ∗ cancelled by Bob’s Step terms
– Coordinate ∗ behaves as in the  = 1 case
Functions

• , = monotone functions over
1 , = Ω  log
• , = -Lipschitz functions over

• ,
= separately convex functions over

• ,
= monotone axis-parallel -th derivative over
• , = convex functions over
– Can’t be expressed as a property of axis-parallel derivatives!
Thm. [BRY] For all these properties 1 = Ω  log
These bounds are optimal for , and , [Chakrabarty,

Open Problems
• Adaptive bounds and round vs. query complexity
tradeoffs for functions [] → ℝ
– Only known:  , = Ω  log  [Fischer’04;