Range avoidance (Avoid) is the computational problem in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$ and the goal is to find a string $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. Avoid was introduced recently by Kleinberg, Korten, Mitropolsky, and Papadimitriou ... more >>>

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 >>>