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.
We consider the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, $\KpolyA$---that is, determining whether a string is time-bounded Kolmogorov random ($K^t$-random) or not---suffices to imply the existence of one-way functions (OWF).
Roughly speaking, our main result shows that under a natural strengthening of standard-type derandomization ...
more >>>
We prove both a conditional and a fully analytic unconditional lower bound against $\mathsf{AC}^0$ circuits for a natural distribution over random satisfiable $3$–CNF formulas with $\Theta(n)$ clauses at constant density.
For any constant depth $d$ and polynomial size $n^k$, such circuits fail to decide satisfiability with probability at least $2/3$ ...
more >>>
We initiate the study of complexity classes ${A^B}$ where ${A}$ and ${B}$ are both ${TFNP}$ subclasses. For example, we consider complexity classes of the form ${PPP^{PPP}}$, ${PPAD^{PPA}}$, and ${PPA^{PLS}}$. We define complete problems for such classes, and show that they belong in ${TFNP}$. These definitions require some care, since ... more >>>
