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.
Can quantum computation become more powerful when operations do not need to follow a definite causal order? We study this question in the process matrix formalism of Oreshkov et al. (Nature Communications, 2012), which allows quantum operations to be connected without a fixed global order. In the computational model, a ... more >>>
We define a notion of Möbius-pseudorandomness for integer sequences generated by multivariate polynomials computed by small and simple algebraic circuits. This mirrors a related definition of Kalai that concerns boolean functions computed by small boolean circuits.
We then prove Möbius-pseudorandomness results for polynomials computed by algebraic circuits with few multiplication ... more >>>
Multiparty Private Simultaneous Messages (PSM), also known as Decomposable Randomized Encoding (DRE) or information-theoretic garbling, is a model for non-interactive secure computation. Each party encodes its input using shared randomness and sends a message to an evaluator who does not know that randomness. The evaluator must recover the function output ... more >>>