Home
Resource
Probabilistic and polynomial methods in additive combinatorics and coding theory
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(587.57 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Kim, John. Probabilistic and polynomial methods in additive combinatorics and coding theory. Retrieved from https://doi.org/doi:10.7282/T3CF9S8H

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleProbabilistic and polynomial methods in additive combinatorics and coding theory
NameKim, John (author); Kopparty, Swastik (chair); Saks, Michael (internal member); Zeilberger, Doron (internal member); Ben-Sasson, Eli (outside member); Rutgers University; Graduate School - New Brunswick
Date Created2016
Other Date2016-05 (degree)
SubjectMathematics, Combinatorial probabilities
Extent1 online resource (viii, 88 p. : ill.)
DescriptionWe present various applications of the probabilistic method and polynomial method in additive combinatorics and coding theory. We first study the effect of addition on the Hamming weight of a positive integer. Consider the first 2n positive integers, and fix an alpha among them. We show that if the binary representation of alpha consists of Theta(n) blocks of zeros and ones, then addition by alpha causes a constant fraction of low Hamming weight integers to become high Hamming weight integers. Our result implies that powering by alpha composed of many blocks requires exponential-size, bounded-depth arithmetic circuits over F_2. We also prove a version of the Cauchy-Davenport theorem for general linear maps. For subsets A, B of the finite field F_p, the classical Cauchy-Davenport theorem gives a lower bound for the size of the sumset A + B in terms of the sizes of the sets A and B. Our theorem considers a general linear map L: F_p^n to F_p^n, and subsets A_1, ..., A_n of F_p, and gives a lower bound on the size of L(A_1 X A_2 X ... X A_n) in terms of the sizes of the sets A_1, ..., A_n. Our proof uses Alon's Combinatorial Nullstellensatz and a variation of the polynomial method. Lastly, we give a polynomial time algorithm to decode multivariate polynomial codes of degree d up to half their minimum distance, when the evaluation points are an arbitrary product set S^m, for every d < |S|. Previously known algorithms can achieve this only if the set S has some very special algebraic structure, or if the degree d is significantly smaller than |S|. We also give a near-linear time algorithm, which is based on tools from list-decoding, to decode these codes from nearly half their minimum distance, provided d < (1 - epsilon)|S| for constant epsilon > 0.
NotePh.D.
NoteIncludes bibliographical references
Noteby John Kim
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3CF9S8H
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024