It is well known that any Linear Threshold Function, $f$,
on $\{ 0, 1\}^n$ has a representation with
integer coefficients with $O(n \log n)$ bits.
We study the problem of finding a small representation
in polynomial time. Given a representation of $f$
with arbitrary size coefficients, we give a polynomial
more >>>

A locally decodable code (LDC) $C: \{0,1\}^k \to \{0,1\}^n$ is an error-correcting code that allows one to recover any bit of the original message with good probability while only reading a small number of bits from a corrupted codeword. A relaxed locally decodable code (RLDC) is a weaker notion where ... more >>>

We survey the notion and history of error-correcting codes and the algorithms needed to make them effective in information transmission. We then give some basic as well as more modern constructions of, and algorithms for, error-correcting codes that depend on relatively simple elements of applied algebra. While the role of ... more >>>