In the last few days, a Denial of Service attack was launched on universities in Israel, leading the administrators of the Israel Academic network to block access to it from the global internet. Consequently, websites such as ECCC have been accessible only from within the Israeli and European academic networks.
It seems that this blocking was just removed, and we hope it will not be put back in the future.
Needless to say, deciding on such blocking is not in our control, but we do apologize for this disruption of service.
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 >>>
