Submissions claiming to resolve a grand challenge, such as the P vs. NP problem, may be rejected without further consideration.
Submissions containing an essential part that seems to be generated by AI tools and/or are written in a way that humans will find hard to understand, may be rejected regardless of their merits. ECCC is intended for communication among humans.
For more details see the Call for Papers.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 construct improved pseudorandom generators for read-$k$ oblivious branching programs with a known reading sequence.
For width-$w$ branching programs over $n$ variables, and designated error $\varepsilon$, our generator has seed length
$$\mathcal{O}\left(n^{1-\frac{1}{2k-1}}\log n\left(k\log w+\log\frac{n}{\varepsilon}\right)\right).$$
This improves upon the previous state-of-the-art due to Gurjar and Volk (ACM ToCT 2020), that has ...
more >>>
We study interactive proofs when the prover and the verifier access the same underlying data through independent noisy views. The noise is \emph{persistent} for each party: each location is corrupted once, and repeated queries to the same location return the same corrupted value. We introduce two models in this setting: ... more >>>
We prove that the XOR of $k$ majorities on disjoint blocks of \(\ell\) bits has correlation at most \((2d/\sqrt{\ell})^k\) with every degree-\(d\) polynomial over \(\mathbb F_2\). By known techniques, this implies pseudorandom generators with polylogarithmic seed length for low-degree polynomials over $\mathbb F_2$ and for alternating circuits with parity ... more >>>
