The classical coding theorem in Kolmogorov complexity [Lev74] states that if a string $x$ is sampled with probability $\geq \delta$ by an algorithm with prefix-free domain, then $K(x) \leq \log(1/\delta) + O(1)$. Motivated by applications in algorithms, average-case complexity, learning, and cryptography, computationally efficient variants of this result have been ... more >>>

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