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.
Pseudorandom generators (PRGs) for low-degree polynomials are a central object in pseudorandomness, with applications to circuit lower bounds and derandomization. Viola’s celebrated construction (CC 2009) gives a PRG over the binary field, but with seed length exponential in the degree $d$. This exponential dependence can be avoided over sufficiently large ... more >>>
In this work, we propose a new bounded arithmetic theory, denoted $\mathbf{APX}_1$, designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer science. Under plausible assumptions, $\mathbf{APX}_1$ is strictly weaker than previously proposed frameworks, such as the theory $\mathbf{APC}_1$ introduced in the seminal work of Je?ábek ... more >>>
We prove a switching lemma for constant-depth circuits over the alphabet $F_p$ with generalized AND/OR gates, extending Tal's Fourier-analytic approach from the Boolean setting. The key new ingredient is a direct computation of the $L_1$ Fourier mass of AND/OR gates over $F_p$, which yields an exact closed-form expression for the ... more >>>
