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.
Trevisan and Vadhan [TV, FOCS'00] constructed (seedless) extractors for distributions samplable by poly-size circuits that have very high min-entropy, under the very strong complexity theoretic hardness assumption that $\text{E}=\text{DTIME}(2^{O(n)})$ requires size $2^{\Omega(n)}$ circuits that have oracle access to $\Sigma_6^{\text{P}}$. In this paper we give three new explicit constructions of extractors ... more >>>
Given a joint distribution $P_{XY}$ of random variables $X,Y$ on finite alphabets, the information
bottleneck method seeks a representation $T$ of $X$ that is as informative as possible about $Y$ while compressing $X$; the privacy funnel asks for a representation that discloses much about $X$ while leaking little about $Y$. ...
more >>>
We construct an explicit family of total sign matrices whose sign-rank is exponentially larger than their margin complexity. Previously, no superpolynomial separation was known for total matrices. In particular, we give a quantitative answer to a question of Linial, Mendelson, Schechtman, and Shraibman (Combinatorica, 2007), who asked whether the logarithmic ... more >>>
