The solution space geometry of random linear equations

Details The solution space geometry of random linear equations The solution space geometry of random linear equations

2011-07-27

arxiv.org/abs/1107.5550v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider random systems of linear equations over GF(2) in which every equation binds k variables. We obtain a precise description of the clustering of solutions in such systems. In particular, we prove that with probability that tends to 1 as the number of variables, n, grows: for every pair of solutions \sigma, \tau, either there exists a sequence of solutions \sigma,...,\tau, in which successive elements differ by O(log n) variables, or every sequence of solutions \sigma,...,\tau, contains a step requiring the simultaneous change of \Omega(n) variables. Furthermore, we determine precisely which pairs of solutions are in each category. Our results are tight and highly quantitative in nature. Moreover, our proof highlights the role of unique extendability as the driving force behind the success of Low Density Parity Check codes and our techniques also apply to the problem of so-called pseudo-codewords in such codes.

Affiliated with

Also associated with

No associations

Rating

The solution space geometry of random linear equations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The solution space geometry of random linear equations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The solution space geometry of random linear equations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-113897