The ECCC has just relocated at the Weizmann Institute of Science. The previous locations were first at the University of Trier (1994-2004), and then at the Hasso Plattner Institute (2004-2016).
Our new URL is eccc.weizmann.ac.il, and the previous URL (eccc.hpi-web.de) is supposed to redirect to the new location. All hyperlinks to reports are still functional after the transition.
Our first priority at the next couple of weeks is to verify that the transition has been performed smoothly and that all existing features work as they used to. (Later on and as circumstances permit, we shall perform various minor improvements, which were on our TODO list for a while.)
Please inform Amir Gonen (amir.gonen@weizmann.ac.il), while CCing Oded Goldreich (oded.goldreich@weizmann.ac.il), as soon as you discover anything that does not function as it used to.
At this point, I would like to thank Christoph Meinel, who has been one of the founders of ECCC and served as its chief editor and head of its local office for 23 years. Special thanks also to Christian Willems, who has provided the technical support for the operation of ECCC for the last few years and has supervised the current transition from the sending side. (I am aware that others deserves much credits as well, but regret that I cannot provide the relevant details at this time. Providing a full account of the history of the establishing of ECCC and its operation since 1994, in the form of a "History of ECCC" page, is on our TODO list.)
Lastly, many thanks to Amir Gonen for performing the transition on the receiving side and for agreeing to undertake the operation from this point on.
Oded Goldreich
After 23 years of running the ECCC, first at the University of Trier, then at the Hasso Plattner Institute, the ECCC will find a new home at the Weizmann Institute.
This smooth transition will happen with the beginning of 2017. We will keep you informed upfront.
We review some semantic and syntactic complexity classes that were introduced to better understand the relationship between complexity classes P and NP. We also define several new complexity classes, some of which are associated with Mersenne numbers, and show their location in the complexity hierarchy.
more >>>We investigate the size complexity of proofs in $RES(s)$ -- an extension of Resolution working on $s$-DNFs instead of clauses -- for families of contradictions given in the {\em unusual binary} encoding. A motivation of our work is size lower bounds of refutations in Resolution for families of contradictions in ... more >>>
In a Nisan-Wigderson design polynomial (in short, a design polynomial), the gcd of every pair of monomials has a low degree. A useful example of such a polynomial is the following:
$$\text{NW}_{d,k}(\mathbf{x}) = \sum_{h \in \mathbb{F}_d[z], ~\deg(h) \leq k}{~~~~\prod_{i = 0}^{d-1}{x_{i, h(i)}}},$$
where $d$ is a prime, $\mathbb{F}_d$ is the ...
more >>>
