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.
This paper is motivated by basic complexity and probability questions about permanents of random matrices over small finite fields, and in particular, about properties separating the permanent and the determinant.
Fix $q = p^m$ some power of an odd prime, and let $k \leq n$ both be growing. For ... more >>>
In this paper we study a basic and natural question about Fourier analysis of Boolean functions, which has applications to the study of Matching Vector based Private Information Retrieval (PIR) schemes.
For integers $m,r$, define a {\em delta function} on $\{0,1\}^r \subseteq \mathbb Z_m^r$ to be a function $f: ... more >>>
We initiate a systematic study of TFZPP, the class of total NP search problems solvable by polynomial time randomized algorithms. TFZPP contains a variety of important search problems such as Bertrand-Chebyshev (finding a prime between $N$ and $2N$), refuter problems for many circuit lower bounds, and Lossy-Code. The Lossy-Code problem ... more >>>
