### Slides - Events @ CSA Dept., IISc Bangalore

```Algebraic Property Testing:
A Unified Perspective
Arnab Bhattacharyya
Indian Institute of Science
Property Testing
Distinguish between
and
and
Property P
-far from property P
Testing and Learning

Proper learning (with membership queries) is as hard
as testing, for any property

For many natural properties, testing is much easier
than learning

Learning always requires time at least as large as size
of hypothesis but testing can be in constant time!
A brief history

Initially appeared as a tool for program checking [BlumLuby-Rubinfeld ‘90]

[Babai-Fortnow-Lund ’90, Rubinfeld-Sudan ’96]: application
to PCPs and low-degree testing

[Goldreich-Goldwasser-Ron ‘98] considered property testing
as full-fledged computational problem in its own right

Now, many other variants and connections known (e.g.,
implicit learning, active testing, coding theory,
inapproximability, …)
Testable Properties
Property P is testable if there exist functions  and  and a
randomized algorithm A such that, given an input object
and a parameter :
•
A makes () queries into input object
•
A rejects with prob. ≥ () if input is -far from P and
with prob. 0 if  = 0

Positive at
>0
Zero at  = 0
ϵ
Testing all-orangeness
P = {all-orange rectangle}
• =1
• Query hits non-orange region with
probability ≥
Testing linearity
P = {linear functions : {, } → {, } }
000…
0
000…
1
001…
1
001…
1
010…
1
010…
0
100…
0
100…
1
101…
1
111…
0
111…
0
Functions of the form
101…
1
, … ,  =  +  + 110…
+ ⋯0+
110…  1
over characteristic011…
2
011…
0
1
• =3
•   +   ≠   +  with probability Ω(). [BlumLuby-Rubinfeld]
Testing low-degree
P = {polynomials :  →  of degree ≤ } }
Functions of the form
, … ,  =

⋯ ⋅   ⋯
Check that function restricted
to a random O(1)-dim
+⋯+ ≤
subspace is poly of degree ≤
over characteristic p
Test detects a violation with probability Ω() [KaufmanRon, Haramaty-Shpilka-Sudan]
Affine-invariant properties
Subject of this talk: “algebraic properties” of
multivariate functions over finite fields.
Definition (affine-invariant property):
If a function f on domain  satisfies an
affine-invariant property P, then  ∘  must
also satisfy P for every affine map :  →

[Kaufman-Sudan]
Why?
Introspective:
 A principled understanding of testability (~
VC dimension theory for PAC learning)
 What kinds of tools are needed to prove
testability? Limitations?
Extrospective:
 Search for locally testable codes (applications
to inapproximability)
Testing Fourier Sparsity
P = {functions : 0,1  → {0,1} have at
most k non-zero Fourier coefficients}
[Gopalan-O’Donnell-Servedio-Shpilka-Wimmer]
showed P is testable (though only with  0 > 0).
Testing Decompositions

P = {functions :  →  that are a product of two

P = {functions :  →  that are the square of a
quartic}

P = {polynomials :  →  of the form  +
where , , ,  are all cubics}
Testability of all such properties open previously!
Main Result
An exact characterization of testability for affineinvariant properties:
Theorem: An affine-invariant property is
testable* if and only if it is locally
characterized
[Joint work with Fischer, H&P Hatami, Lovett ‘13]
Locally Characterized
Definition (locally characterized):
A property P is locally characterized if there
always exists a constant-sized witness to
non-membership in P.
Examples:
• Linearity: If  isn’t linear, then there exist ,  such that
+   ≠ ( + ).
• Low degree: If deg  > , then there exists a point at
which the ( + 1)-th order derivative is nonzero.
Necessity of locality
Theorem: An affine-invariant property is
testable if and only if it is locally
characterized.
Proof of : The set of queries by the tester that
make it reject is itself a -sized witness to nonmembership in the property.
Proof of
: Rest of this talk…
Degree-structural properties

Are properties like “Fourier sparsity”, “product
of two quadratics”, “square of a quartic”, “sum
of two products of quadratics”, “splitting into d
linear forms” locally characterized?
Theorem: Any property described as the
property of decomposing into a known
structure of low-degree polynomials is
locally characterized.
Subsequent work

Degree-structural properties are not only
testable but reconstructible!
◦ Given degree- poly  = 1 2 + 3 4 where
1 , … , 4 are degree-(/2) polys, we can
reconstruct 1 , … , 4 by making ( ) queries to
. [B. ‘14]

Characterization of two-sided testability
[Yoshida ‘14]
Some drawbacks…
Unfolded proof uses
non-constructive
results. We get no
bound on the locality
and query
complexity for even
simple properties
like “product of two
A Running Example: RBG
+
++
Witness to non-membership:

+
RBG square
A function :  → {, , } satisfies the RBG
property if there are no , ,  ∈  such that   =
+  = ,   +  = , and   +  +  =
.
The RBG claim
Claim: The RBG property is testable with 4
queries.
Suffices to show that if :  →
{, , } is far from
RBG, then a random tuple
(,  + ,  + ,  +  + ) is an
RBG square with constant
probability.
+

++
+
Dreams of a proof
The dreamiest situation
Suppose non-RBG function  has the form:
() = Γ 1 , 2 , … ,
(0,4)
•  cells of equal size
(0,3)
(0,2)
(0,1)
(0,0)
• Must exist at least one
RBG square
• Probability of selecting
an RBG square is −3 .
A slight nudge
Same analysis works if non-RBG function
has the form:
() = Γ ℓ1  , ℓ2  , … , ℓ ()
where ℓ1 , ℓ2 , … , ℓ are linearly independent
linear forms.
Also works if “linearly
independent” replaced
by “random”
More rocking of the bed
Suppose non-RBG function  has the form:
() = Γ 1  , 2  , … ,  ()
where 1 , … ,  are random bounded degree nonlinear polynomials.
Partitioning by random polys
(0,4)
(0,3)
Joint distribution of
1 , … ,
close to uniform
distribution
(0,2)
(0,1)
(0,0)
cells of roughly
equal size
Partitioning by random polys
(0,4)
(0,3)
(0,2)
Joint distribution of
(1 (), . . ,  (), 1 ( +
), . . . ,  ( + ), 1 ( +
), . . . ,  ( + ), 1 ( +
+ ), . . . ,  ( +  +
))close to uniform
(0,1)
(0,0)
Probability of selecting an
RBG square is ≈ −3 .
Returning to intermediate dream
Suppose non-RBG function  has the form:
() = Γ 1  , 2  , … ,  ()
where 1 , … ,  are arbitrary low degree polynomials.
Instead of insisting 1 , … ,  be truly random, can
we weaken the requirement?
Returning to intermediate dream
Suppose non-RBG function  has the form:
() = Γ 1  , 2  , … ,  ()
where 1 , … ,  are arbitrary low degree polynomials.
How to ensure (1 , … ,  ) distributed close to
uniform? How to even ensure 1 distributed close
to uniform?
High rank polynomials
Theorem [Green-Tao, Kaufmann-Lovett]: A
polynomial :   →  is distributed close to
uniform if Q is of high rank.
Definition: A polynomial :   →  is of rank >  if
there are no polynomials 1 , … ,  of degrees less than
deg(Q) such that
= Λ 1 , … ,
for some function Λ.
High rank polynomial collection
Theorem [Green-Tao, Kaufmann-Lovett]:
Polynomials 1 , … ,  :   →  jointly distributed
close to uniform if every nontrivial linear
combination of 1 , … ,  is high rank.
Polynomial Regularity Lemma
A straightforward inductive argument shows that,
given
() = Γ 1  , 2  , … ,  ()
we can find a high rank collection of polynomials
1 , … ,  ′ such that:
() = Γ′ 1  , 2  , … ,  ′ ()
1 , … ,  ′ form cells of roughly equal size
Equidistribution of squares?
Recall we also wanted equidistribution of squares. Is
high rank sufficient for this purpose?
Wanted Lemma: If 1 , … ,  ′ of sufficiently high
rank, then:
1  , . . ,  ′  ,
1  +  , . . . ,  ′  +  ,
1  +  , . . . ,  ′  +  ,
1  +  +  , . . . ,  ′  +  +
distributed close to uniform.
A bit of a nightmare…
Wanted lemma not necessarily true!
Suppose 1 is of degree 1. Then:
1  − 1  +  − 1  +  + 1  +  +  = 0
identically.
Lesson: some correlations may be present because
of degree, no matter how large the rank is
Corrected equidistribution
Lemma: Given polynomials 1 , … ,  of high rank,
either there’s some linear identity among
,   +  ,   +  ,  ( +  + ) for some i,
or the tuple
1  , . . ,   ,
1  +  , . . . ,   +  ,
1  +  , . . . ,   +  ,
1  +  +  , . . . ,   +  +
is close to uniformly distributed.
Proof uses “Gowers
inverse theorem”
[Tao-Ziegler]
Applying corrected equidistribution

2
2

4

Suppose 1 satisfies: 1  −
1  +  − 1  +  + 1 ( +
Almost awake to reality…
Now, let’s remove all restrictions on RBG-far
function :  → {, , }.
Can we “approximate” f by some function g of
the form:
() = Γ 1  , 2  , … ,  ()
where 1 , … ,  are low degree polynomials?
Regularity Lemma
Given any function :  → {0,1} and integer , there exist
constantly many polynomials 1 , … ,  :  →  of degrees at
most , a function Γ:  → [0,1] and a function ℎ:  → [−1,1]
such that:
•   = Γ 1  , … ,
+ℎ
• Collection 1 , … ,  has high rank
Uses “Gowers
inverse theorem”
[Tao-Ziegler]
• Γ(1 , … ,  ) is the average value of  on the cell indexed
(1 , … ,  )
• ( + 1)-th order Gowers norm of h is small
Victory in dreamland!

Letting   :   → {0,1} be indicator function of color c.
Then, rejection probability is:
,, [      +     +     +  +  ]

We apply the regularity lemma. The term with low
Gowers norm contributes negligibly to expectation.

A combinatorial argument finishes the claim.
Waking up to hard reality

“Inverse conjecture for the Gowers norm is false” [LovettMeshulam-Samorodnitsky]

Turns out that in the conjecture, one needs to modify the
definition of polynomials to include functions that are not valued.

Need to reprove regularity lemma and equidistribution
claims for such “non-classical polynomials” (technical core of
our work)

Also, several lies encountered in this dream sequence
Non-classical polynomials
Definition (non-classical polynomial):
A function :  → ℝ/ℤ is of degree ≤  if
Δℎ1 Δℎ2 ⋯ Δℎ+1  ≡ 0
for any ℎ1 , ℎ2 , … , ℎ+1 ∈  , where:
Δℎ   =   + ℎ − ()
• If range of  is
1 2
−1
0, , , … ,

same as classical
, non-classical
Non-classical polynomials
Definition (non-classical polynomial):
A function :  → ℝ/ℤ is of degree ≤  if
Δℎ1 Δℎ2 ⋯ Δℎ+1  ≡ 0
for any ℎ1 , ℎ2 , … , ℎ+1 ∈  , where:
Δℎ   =   + ℎ − ()
1 1 3
4 2 4
• Function : 2 → 0, , ,
defined as
1
0 = 0,  1 =
4
is non-classical poly of degree 2.
Gowers norm and inverse theorem

For functions :  → ℂ, the Gowers norm of order d measures
the expected multiplicative derivative of  at a random point
in  random directions.

Fact: If Gowers norm of f of order d is 1 and f takes values
inside the unit disk, then f is the exponential of a non-classical
polynomial of degree ≤  − 1.

Gowers Inverse Theorem: If Gowers norm of f of order d is
> 0 and f takes values inside the unit disk, then f is
correlated with a non-classical polynomial of degree ≤  − 1.
Open Questions

Proof for degree-structural property also uses the same
core technical ideas, so no good locality bounds even for
“simple” properties like product of two quadratics.

Give non-trivial lower bound for testing any natural
affine-invariant property. No superpolynomial lower
bounds known in 1/.

Find other uses of equidistribution of high rank
polynomials.
THANK YOU!
```