Application of Parvaresh Vardy Codes: Guruswami-Umans-Vadhan Expander Construction

The contents of this page are licensed under the Creative Commons Attribution-Sharealike 3.0 License.


Application of Parvaresh Vardy Codes: Guruswami-Umans-Vadhan Expander Construction


Overview

Expanders are highly connected yet sparse graphs. They have a wide variety of applications in theoretical computer science, in designing algorithms, to construct hash functions in cryptography, error correcting codes, extractors, pseudorandom generators, sorting networks and robust computer networks.
The construction of expanders of Guruswami-Umans-Vadhan is based on the list decodable codes of Parvaresh and Vardy.

Introduction

Let us review the basics of list decodable codes. We take C as the code which is a mapping $  C: \left[N\right] \mapsto \left[M\right]^D $ encoding messages of bit length $  n= \log_2 \left[N\right]  $ to$  D   $ symbols over the alphabet $  \left[M\right].  $ Rate of such a code will be $  \rho= n/ \left(D \log_2 M\right) $. We call $ C $ as $ \left(\varepsilon,K\right) $ list decodable if for every$  r \in [M]^D $, the set LIST$ \left(r,\varepsilon\right) =^{def} \left{x : Pr_y\left[C\left(x\right)_y = r_y\right] \geq \varepsilon \right}  $ is of atmost K size. With list decodable codes, we wish to optimize the tradeoff between the agreement $ \varepsilon $ and the rate $ \rho $ which do not depend on message length M.
Sudan showed that such a property can be achieved by Reed Solomon Codes in polynomial time. This tradeoff was then improved by Guruswami and Sudan and recently by Parvaresh and Vardy who improved the tradeoff by using a variant of Reed Solomon codes.

GUV Constructor

The construction of Guruswami-Umans-Vadhan Expander is based on Parvaresh Vardy codes.We know that a typical Parvaresh Vardy codeword has several related degree $ m-1 $ polynomials $ f_0,f_1,f_2...f_{m-1} $ evaluated at all points in the field and $ f\in \mathbb{F}_q\left[Y\right] $ where $ q $ is a prime power over which the field $ \mathbb F $ is defined. All such evaluations are packaged into larger alphabet $ \mathbb{F}_{q^m} $ symbol. This extra redundancy enables a better list decoding algorithm than Reed Solomon ones.
Elements of $ \mathbb{F} $ are chosen such that $ f_i= {f_0}^{h^i} $ for $ i\geq1 $ and $ h\geq1 $ integer parameter.

We need to show that for a given set $ T $ of size $ L $, the set LIST$ \left(T\right)=\{f_0:\Gamma \left(f_0\right)\subseteq T \} $ is small.

Expander Graphs

Lets start with some definitions : For a bipartite graph $ \Gamma: \left[N\right] \times \left[D\right] \mapsto \left[M\right]  $ and a set $  T \subseteq \left[M\right] $, define $  LIST\left(T\right) =\{x \in \left[N\right] :\Gamma\left(x\right) \subseteq T \} $.
Also, a digraph $ G $ is a $ \left(K,A\right) $ vertex expander if for all sets $ S $ of at most $ K $ vertices, the neighborhood $ N\left(S\right) $ is of size atleast $ A.|S| $ where neighborhood $ N\left(S\right)=^{def} \{u | \exists v \in S $ s.t. $ \left(u,v\right) \in E\} $. Details can be found out in the paper Expander graphs and vertex expansion.
This proves the following lemma:

Lemma- A graph $ \Gamma $ is a$  \left(K,A\right) $ expander if and only if for every set $ T $ of size at most $ AK-1, LIST\left(T\right) $ is of size at most $ K-1 $.

Construction


Fix the field $ \mathbb F_q $ and let $ E\left(Y\right) $be an irreducible polynomial of degree $ n $ over the field $ \mathbb F_q $. Elements of $ {\mathbb F_q}^n $ are univariate polynomials over $ \mathbb F_q $ with degree at most $ n-1 $. $ h $, integer parameter is fixed.
The expander is bipartite graph $ \Gamma_{PV}: {\mathbb F_q}^n \times \mathbb F_q \mapsto {\mathbb F_q}^{m+1}  $ defined as:
$ \Gamma\left(f,y\right) =^{def} \left[y,f\left(y\right),\left(f^h \mod E\right)\left(y\right),\left(f^{h^2} \mod E\right)\left(y\right),...,\left(f^{h^{m-1}} \mod E\right)\left(y\right)\right]. $-----------------------------------------------$ \left(1\right)  $
The bipartite graph has message polynomials on the left and the $ j^{'th} $ neighbor of $ f\left(Y\right) $ is the $ j^{'th} $ symbol of Parvaresh-Vardy encoding of $ f\left(Y\right) $. This follows a theorem which can formally be stated as:

Theorem 1: The graph $ \Gamma_{PV}: {\mathbb F_q}^n \times \mathbb F_q \mapsto {\mathbb F_q}^{m+1}  $ is a $ \left(\leq K_{max},A\right) $ expander for $ K_{max}=h^m  $ and $ A=q-\left(n-1\right)\left(h-1\right)m $.

Proof: Let us take any integer $ K $, where $  K\leq K_{max}=h $ and let $ A=q-\left(n-1\right)\left(h-1\right)m $. By the lemma defined above, if we take a $ T $ such that $ T\subseteq {\mathbb F_q}^{m+1} $ is of at most $ AK-1 $ size, then we need to show that $ |LIST\left(T\right)|\leq K-1 $.

Parvaresh-Vardy codes view degree $ n-1 $ polynomials as elements of field $ \mathbb{F}=\mathbb{F}_q\left[Y\right]/ E\left(Y\right) $ where $ E $ is an irreducible polynomial of degree $ n $. We need $ Q $ that will have non zero coefficients on monomials of the form $ X^i M_j\left(X_1,....,X_m\right) $ for $ 0\leq i \leq A-1 $ and $ 0\leq j \leq K-1\leq h^m-1 $, where $ M_j\left(X_1,...,X_m\right) = {X_1}^{j_0}....{X_m}^{j_{m-1} $ and $ j=j_0+j_1h+...+j_{m-1}h^{m-1} $ is the base-$ h $ representation of $ j $. If we impose a homogeneous linear constraint on $ AK $ coefficients of $ Q $, then we require that $ Q\left(z\right) = 0 $ for every $ z\in T $. Since number of constraints is less than the number of unknowns, the linear system thus made has a solution that is not 0. If $ Q $ has the smallest possible degree in variable $ X $, then

$ Q\left(X, X_1,....,X_m\right) = {\Sigma_{j=0}}^{K-1}p_j\left(X\right). M_j\left(X_1,...,X_m\right) $-------------------------------------------------------$ \left(2\right) $
for univariate polynomials $ p_0\left(X\right),...,p_{K-1}\left(X\right) $, at least one of $ p_j $ will not be divisible by $ E\left(X\right) $. If every $ p_j $ is divisible by $ E\left(X\right) $ then $ Q\left(X, X_1,....,X_m\right) / E\left(X\right) $ will have smaller degree in $ X $ and would still vanish on $ T $ (since $ E $ is irreducible and therefore has no roots in $ \mathbb {F}_q $).

Let us take $ f\left(X\right) \in LIST\left(T\right) $ to be any polynomial. Then by our $ Q $,
$ Q\left(y, f_0\left(y\right),  f_1\left(y\right),.....,  f_{m-1}\left(y\right)\right) = 0 $ $ \forall y \in \mathbb F_q $.
This means, the univariate polynomial $ R_f\left(X\right) =^{def} Q\left(X, f_0\left(X\right),  f_1\left(X\right),.....,  f_{m-1}\left(X\right)\right) $ has $ q $ zeroes. Since $ R_f\left(X\right) $ has at most degree $ \left(A-1\right)+\left(n-1\right)\left(h-1\right)m < q $, then it is $ 0 $. Refer Polynomials and properties for proof. So,

$ Q\left(X, f_0\left(X\right),  f_1\left(X\right),.....,  f_{m-1}\left(X\right)\right)=0 $

Recall that, we have, $ f_i\left(X\right) \equiv f\left(X\right)^{h^i} \left( \mod E\left(X\right)) $. Thus,
$ Q\left(X,f\left(X\right),f\left(X\right)^h,....,f\left(X\right)^{h^{m-1}}\right) \equiv Q\left(X,f_0\left(X\right),...,f_{m-1}\left(X\right) \equiv 0 $ ----------------- $ \left[0\left( \mod E\left(X\right)\right)\right] $.

Then $ f\left(X\right) $ which is an element of the extended field $ \mathbb{F}=\mathbb{F}_q\left[Y\right]/ E\left(Y\right) $ $ \left( $where $ E $ is an irreducible polynomial of degree $ n $$ \right) $ is the root of univariate polynomial $ Q^* $ over $ \mathbb F $ defined by

$  Q^*\left(Z\right) =^{def} Q\left(X,Z,Z^h,Z^{h^2},...,Z^{h^{m-1}}\right) \mod E\left(X\right)  $
From equation $ \left(2\right) $, the above equation is same as:
$ = \Sigma_{j=0}^{K-1} \left(p_j\left(X\right) \mod E\left(X\right)\right) . M_j\left(Z,Z^h,...,Z^{h^{m-1}}\right) $
$ = \Sigma_{j=0}^{K-1} \left(p_j\left(X\right) \mod E\left(X\right)\right) . Z^j $

Since this is true for all $ f\left(X\right)\in LIST\left(T\right) $, $ Q^* $ has at least $ |LIST\left(T\right)| $ roots in field $ \mathbb F $. Some $ p_j\left(X\right) $'s is not divisible by $ E\left(X\right) $, $ Q^* $ is a non zero polynomial. Thus, $ |LIST\left(T\right)| $ is bounded by the degree of $ Q^* $, which is at most $ K-1 $.

By proper instantiation of parameters in Theorem 1, we lead to following results:
Theorem 2: For all positive integers $ N $, $ K_{max} \leq N $, all $ \varepsilon >0 $, and all $ \alpha \in \left(0,\log x/ \log\log x\right) $ for $ x= \left(\log N\right)\left(\log K_{max}\right) / \varepsilon $, there is an explicit $ \left( \leq K_{max}, \left(1-\varepsilon\right)D\right) $ expander $ \Sigma : \left[N\right] \times \left[D\right] \mapsto \left[M\right] $ with degree $ D= O\left( \left(\left(\log N\right)\left{(\log K_{max}\right) / \varepsilon\right)}^{1+{1/\alpha}}\right) $ and $ M \leq D^2. {K_{max}}^{1+\alpha} $. Moreover, $ D $ and $ M $ are powers of $ 2 $.

Theorem 3: For all positive integers $ N $, $ K_{max} \leq N $, and all $ \varepsilon >0 $, there is an explicit $ \left( \leq K_{max}, \left(1-\varepsilon\right)D\right) $ expander $ \Sigma : \left[N\right] \times \left[D\right] \mapsto \left[M\right] $ with degree $ D \leq 2\left(\log N\right)\left{(\log K_{max}\right) / \varepsilon} $ and $ M \leq {\left(4K_{max}\right)}^{\log D} $. Again, $ D $ and $ M $ are powers of $ 2 $..

The proofs of the above two theorems can be found from GUV paper.

References


1. Unbalanced Expanders and Randomness Extractors from Parvaresh–Vardy Codes - GUV paper.

2. Expander graphs.

3. Farzad Parvaresh and Alexander Vardy. [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?
arnumber=1530722&contentType=Conference+Publications Correcting errors beyond the Guruswami-Sudan radius in polynomial time] In
Proceedings of the 43nd Annual Symposium on Foundations of Computer Science (FOCS), pages 285-294, 2005.

4. Atri Rudra. Error Correcting Codes: Combinatorics, Algorithms and Applications Lecture 41

5. Madhu Sudan. Essential coding theory Lecture 15 and Lecture 16

6. Expander graphs and vertex expansion.

7. bipartite graph.

8. digraph.

9. Polynomials and their properties.

10. Parvaresh Vardy codes