Additive Combinatorics in Theoretical CS: Linearity Testing and Applications
Explore the world of linearity testing and additive combinatorics in theoretical computer science through methods such as property testing, discrete Fourier transform, and character maps. Discover how to analyze functions and data for specific properties efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Linearity Testing Additive Combinatorics and its Applications in Theoretical CS Section 2.5 Shachar Lovett Presented by Oleg Zlydenko
Plan Motivation Discrete Fourier Transform BLR linearity testing Testing linear maps
Motivation 1/4
Property Testing Test if a (large) data has some property Often hard, the testing is probabilistic If the data has the property return True w.h.p If it s far from the property return False w.h.p Examples: Is a function linear? Is a graph connected? Approximate the average of a function
Motivation Motivation for property testing: Large data impossible to verify for certain Being close to the property is often enough Use the probabilistic testing as a preliminary stage
Linearity Testing Intuitively, a function ? is far from linear if we must change many of values of ? to make it linear The na ve algorithm works very well Query ? ? ,? ? ,?(? + ?) Test if ? ? + ? = ? ? + ?(?) We will analyze: The case ?2 The case ?2 Extensions to other fields are possible ? ?2, using Fourier Transform ? ?2 ?, using Additive Combinatorics
Characters A character ?:? is a map where ?1,?2 ?: ? ?1?2 = ? ?1?(?2) Left hand side multiplication in group Right hand side multiplication in ?, and all ? ?: ?,?are characters For ? = 2 ??? = 1 Note that ??? = ??(?)
The Dual Group Lemma: The product of two characters ?1,?2:? is also a character Proposition: The set of characters of an abelian group ? forms a group ?, the dual group of ? In addition, ? is isomorphic to ? So in the case ? = ?2 ?2 Proof: exercise ?, ? ?= ??:? ?2
Inner Product We can define an inner product on functions ?,?:? : ?,? = ? ? ?? ? ?(?) Why is it an inner product? Lemma: ?2 1 ? ?forms an orthonormal basis for functions ?2 ?: ??,?? = 1 ?? ? = ? For ?,? ?2 0 ?? ? ? Since ?0? = 1: ? ???? = 0 for all ? 0
Proof of Orthonormality 1 ? ? ?2 ??,?? = ???? ??? = ?2 2 ? ? ?2 2 ? ? ?2 If ? = ?, ? + ?,? = 0,? = 0, so the sum is 1. If ? ?, choose some index ? s.t: ??+ ??= 1 Denote by ? be the unique element in ?2 from ? only at index ? 1 We can pair all of the elements in ?2 ?,? 1 ?,?= ? 1 ?+?,? ? 1 ?such that ? differs ?+?,?+ 1 ?+?,? = 0 ?in such a way
Fourier Expansion ? can be decomposed as a (unique) Any function ?:?2 linear combination of characters The decomposition is called the Fourier expansion: ? ? = ? ? ?(?) ??? The Fourier coefficients are ?(?) = ?,?? 1 ? ? ?? ? 2 2= ? ? ?(?) Parseval s Identity:
Distance ? ?2 We define the distance between 2 functions ?,?:?2 as: 1 2? ? ?2 The fraction of elements in which they differ ???????= ? ? = ?=1 linear functions ?2 The distance of ? from being linear is: ???? ?,??????? = ?:? ? ? ? ???? ?,? = ? ?is the set of ????:? ?2 ? ?2 ? ???????????(?,?) min
Motivation Let ? ? = 1? ? The Fourier coefficients of ? measure the distance of ? from all linear functions Proof: Let ? ? = ?,? be some linear function ? ? = ?,?? = 2 ? ? ?2 2 ? ? ?2 2 ? ?:? ? = ? ? 1 2 ???? ?,? ?? ? ??? = ? 1? ? +? ?= ?:? ? ? ? =
BLR 3/4
BLR test ?, query Choose randomly and uniformly ?,? ?2 ? ? ,? ? ,?(? + ?) If ? ? + ? ? ? + ?(?), BLR rejects ? Otherwise, BLR accepts ? Theorem (Blum-Luby-Rubinfeld): Let ?:?2 If ? is linear the BLR test always accepts ? If ???? ?,??????? ?, BLR rejects ? with probability at least ? ? ?2
BLR Theorem Proof 1/4 If ? is linear it is obvious that BLR accepts ? Assume ???? ?,??????? = ? Let ? ? = 1? ? The Fourier coefficients of ? measure the distance of ? from all linear functions ? ? = 1 2 ???? ?,? 1 2 ?
BLR Theorem Proof 2/4 Consider ? ?,? = ? ? + ? ? ? ?(?) ? ?,? = 1 ?? ? ? + ? = ? ? + ?(?) 1 ?? ? ? + ? ? ? + ?(?) ??,? ?2 Pr ? ? + ? = ? ? + ? ? ? ? + ? ? 2 Pr BLR accepts f 1 ? ? ?,? = Pr ? ? + ? = We want to bound ??,? ?2 expansion using Fourier ? ? ?,? ? ? 1 2 ?
BLR Theorem Proof 3/4 Using Fourier expansion on ?: ??,? ?2 ? ? ?,? = ??,? ?2 ? ? ? ? ? ?(? + ?) = ? ? ? ??? ? ?2 ? ? ? ??? ? ?2 ? ? ? ??( ? ?2 = ??,? ? + ) ? ? ? ? ? ? ? ? ??,? ?2 ?,?,? ?2 ? ??? ??? ??? + ? = ? ? ? ? ? ? ? ??,? ?2 ?,?,? ?2 ? ??+?? ??+?? = ? ? ? ? ? ? ? ?? ?2 ?,?,? ?2 ? ??+?? ?? ?2 ? ??+?? = 2 Pr BLR accepts f 1 ? ? 1 2 ? ??,? ?2 ? ? ?,?
BLR Theorem Proof 4/4 ??,? ?2 ?,?,? ?2 Recall: ? ???? = 0 for all ? 0 ? ? ?,? = ? ? ? ? ? ? ? ?? ?2 ? ??+?? ?? ?2 ? ??+?? ? ??(?) = 0,? 0 ?? ?2 1,? = 0 ? ? ?3 = ? ?2 ??,? ?2 Using Parseval s identity (1 ? ? ?,? 2): 2= ? ? ?(?) ? ? ?? ? ? ? ?3 = ? ?2 = 1 2 ? 2 Pr BLR accepts f 1 = ??,? ?2 max ? ?2 ? ? ?,? ? ? ? ? ?2= max ? ? ? ?2 ? ? ? ?2 Pr BLR accepts f 1 ? = 2 Pr BLR accepts f 1 ? ? 1 2 ? ??,? ?2 ? ? ?,?
Important Remark The probability of falsely reporting linear can be improved Repeat BLR test several times Accept ? if all iterations were successful Full analysis is out of our scope
Agreement For the next theorem, it s more convenient to measure the agreement of functions: ????? ?,? = 1 ????(?,?) We define the agreement of ? with linear maps in a similar fashion: ???????,? is the set of linear maps ?:?2 ????? ?,???????,? = ? ?2 ? ? ???????,??????(?,?) max
Testing Linear Maps Theorem (Samorodnitsky): Let ?:?2 Consider the test: Choose ?,? ?2 Query ? ? ,? ? ,?(? + ?) If ? ? + ? = ? ? + ?(?) accept ?, otherwise reject If the test accepts ? with probability ? > 0, then ? ?2 ? be a map ? uniformly at random ? 1 1 ? ????? ?,???????,? exp
Reminders Theorem (Ruzsa): ? is an Abelian group of torsion ? ? ? with ? + ? ?|?| exists A ? < ? of size ? ?2 ??4 ? Theorem (Balog-Szemeredi-Gowers): ?,?,? ? sets ? = ? = ?, ? = ?? Assume: Pr ? ?,? ? ? + ? ? ? Then exist ? ?,? ? s.t. ? , ? ?2 16 ? and 5 1 ? ? + ? 212 ?3 ? ? + ? ???? ?,1/? ?
? 1 1 ? ????? ?,???????,? exp Samorodnitsky Theorem Proof 1/5 Assume the test accepts ? w.p ? Let ? = ?,? ? :? ?2 Pr ?,? ?? + ? ? = Pr ?,? ?2 Pr ?,? ?2 We can apply BSG: ? ?2 ?+? ? + ?,? ? + ? ? ? = ? ?? ? + ? = ? ? + ? ? ? ? 1 1 ? ? ?, ? ?? 1 2? and ? + ? ?
? 1 1 ? ????? ?,???????,? exp Samorodnitsky Theorem Proof 2/5 ? ?2 ?+? and We have: ? ? = ?,? ? :? ?2 ? 1 1 ? ? + ? ? Applying Ruzsa s theorem we get: A subspace ? ? ?2 ?+? ? 1 1 ? ? ?(?) ? , where ?(?) = exp ? ?2 ? We want to use ? to construct a linear map ?:?2 such that ?????(?,?) is large enough
? 1 1 ? ????? ?,???????,? exp Samorodnitsky Theorem Proof 3/5 ? ?2 ?+? and We have: ? ? = ? ? ?2 Let ? = ? ?2 ? is a subspace of ?2 Let dim ? = ? and ?1, ,?? ?2 Also ?1, ,?? ?2 Let ?1:?2 Finally, let ? = ? is a subspace of ?, ? = |?| ?,? ? :? ?2 ?+?, ? ?(?)|? | ?: ? ?2 ?, and ? ? ?, ?,? ? ? a basis of ? ?, such that ??,?? ? ? a linear map s.t. ?1?? = ?? ?,?1? :? ? ? ?2
? 1 1 ? ????? ?,???????,? exp Pause for intuition We have: ? ? = ? ?? 1 2? ? ? ?2 ? = ? = ? |? | Intuition: ? ? is a lower bound on ?????(?,?1) ? ? + ? is a lower bound on ?????(?,?1+ ?) ?1+ ?is an affine function, but we ll fix it later ? ?2 ?+?, ?,? ? :? ?2 ?+?, ? ?(?)|? | ?,?1? :? ? ?
? 1 1 ? ????? ?,???????,? exp Samorodnitsky Theorem Proof 4/5 We have: ? ? = ? ? ?2 ? = ? = ? |? | ? ?2 ?+?, ? ?? 1 2? ?,? ? :? ?2 ?+?, ? ?(?)|? | ?,?1? :? ? ? ? ? can be decomposed as a disjoint union of ? ?) There must exist ? ? s.t.: |?| cosets of ? (? + ? for ? 1 ? ? ? ? 1 ? ? ? + ? ? ?(?)= exp ????? ?,?1+ ? 2 ? ? ? + ? ?? 1/?(?)
? 1 1 ? ????? ?,???????,? exp Samorodnitsky Theorem Proof 5/5 We have: ????? ?,?1+ ? ?? 1/?(?) Denote: ? ? = ?1? + ?2? ?, where ?2:?2 Note that given ? ?2 we have ?2? = 1 for exactly 2? 1 ??2????? ?,? = ? ?2 ? ?2 is a linear function ? (? 0), out of the 2? options for ?2, ?Pr?2 ?2? = 1 ? ? = ?1? + ? ?? 1 2?(?) 2 ? 1 2 Pr? ?2 ? ? ? = ?1? + ? 2 ? ?? 1 2?(?) 2 ? Hence, for some ?2: ????? ?,?
Improvements Proving a better bound for ? ? directly provides a better bound for the linearity testing A later result by Sanders improves the bound to: ? 1 1 ? ????? ?,???????,? exp log A polynomial bound is conjectured, and is equivalent to the polynomial Freiman-Ruzsa conjecture
