# Browsing by Subject "Error-correcting codes (Information theory)"

Now showing 1 - 2 of 2

- Results Per Page
1 5 10 20 40 60 80 100

- Sort Options
Ascending Descending

Item Error correcting codes: local testing, list decoding, and applications(2007-12) Patthak, Anindya Chandra, 1977-; Zuckerman, David I.Show more This dissertation is a study of special types of error correcting codes and their applications. It consists of three parts. First, we study Generalized Reed-Muller codes (over prime fields), aka low-degree polynomials. Specifically, we show that these codes are locally testable. Locally testable codes are a class of error-correcting codes with the property that given (black-box access to) a word, it is possible to determine with high probability whether the given word is close to a codeword by querying randomly at a sublinear number of places. Such codes are known to be useful for efficient constructions of probabilistically checkable proofs. Our analysis also enables us to obtain a self-corrector for the given function, in case the function is reasonably close to a codeword. Specifically, we show that the value of the function at any given point may be obtained with good probability by querying the function on a few random points. Utilizing pairwise-independence an even higher probability can be achieved by querying the function on slightly more random points and using majority logic decoding. Our result implies that if the acceptance probability is low, then the function is far from low-degree polynomials. Is it possible to estimate the distance even when the received word is far from low-degree polynomials? We could achieve only a conditional result on this front. Specifically, we observe that under certain condition the Gowers uniformity norm estimates the proximity of a function to a low-degree polynomial. Second, we study efficient constructions of optimal list decodable codes. List decodable codes are error-correcting codes that can deal with highly noisy channels. When a received word has too many errors, unambiguous decoding is no longer possible. A plausible alternative in such a circumstance is to output a small list of possible codewords, each having some minimum agreement with the received word. This is known as the list decoding problem. It is known that good list decodable codes exist. We construct a new family of error-correcting codes based on algebraic curves over finite fields and present efficient list decoding algorithms for the family. These codes extend the class of algebraic-geometric (AG) codes via a generalization of the approach in the recent breakthrough work of Parvaresh and Vardy [PV05]. Third, we develop a new technique to lower-bound the minimum distance of certain types of quasi-cyclic codes with large dimension by reducing the problem to lower-bounding the minimum distance of a few significantly smaller dimensional codes. Using this technique, we prove that a code similar to the SHA-1 (Secure Hash Algorithms) message expansion code has minimum distance at least 82, and that too in just the last 64 of the 80 expanded words. We use this new code to propose an improvement upon the widely used cryptographic hash function SHA-1.Show more Item Error-correcting codes on low néron-severi rank surfaces(2006) Zarzar, Marcos Augusto; Voloch, José FelipeShow more In this work we construct and estimate the parameters of error-correcting codes on algebraic surfaces whose N´eron-Severi group has low rank. If the rank of the N´eron-Severi group of a surface is 1, the intersection of this surface with an irreducible surface of lower degree will be an irreducible curve, and this allows the construction of ”good” codes and we can have a good estimate for its parameters. Surfaces with rank 1 and many points are not easy to find, but we are able to find some surfaces with low rank that gave us ”good” codes too. We also present an efficient decoding algorithm for such codes. It is based on the realization of the code as an LDPC code, and it was inpired by the Luby-Mitzenmacher algorithm.Show more