WEBSITE > HOME:

#### What we do and why

The Electronic Colloquium on Computational Complexity was established in 1994 as a forum for the rapid and widespread interchange of ideas, techniques, and research in computational complexity. The purpose of this Colloquium is to use electronic media for scientific communication and discussions in the computational complexity community. The Electronic Colloquium on Computational Complexity (ECCC) welcomes papers, short notes, and surveys with -
• relevance to the theory of computation,
• clear mathematical profilei, and
• strictly mathematical format.

#### Central topics

• models of computation and their complexity.
• complexity bounds and trade-offs (with the emphasis on lower bounds).
• complexity theoretic aspects of specific areas including coding theory, combinatorics, cryptography, game theory, logic, machine learning, optimization, property testing, and quantum computation.
For more details see the Call for Papers.

Here are some papers on the idea and concept of electronic colloquia and ECCC.
• Christoph Meinel, Volker Klotz
Communications of the ACM - CACM, vol. 49, no. 1, pp. 131-134, 2006.
• Jochen Bern, Carsten Damm, Christoph Meinel
European Conference on Digital Libraries - ECDL, pp. 405-421, 1997.
5th January 2017 18:30

#### ECCC relocated to Weizmann Institute

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

23rd December 2016 12:53

#### ECCC moves to Weizmann Institute

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.

4th March 2016 14:00

#### ECCC Archive DVD 2015

209 reports have been published on ECCC in 2015. The collection of all these reports is now available on DVD. You can order the archive (and also the archive DVDs from earlier years) at the local office. Please email eccc@eccc.hpi-web.de for ordering.

-> Older news
TR17-011 | 22nd January 2017
Boaz Barak, Pravesh Kothari, David Steurer

#### Quantum entanglement, sum of squares, and the log rank conjecture

For every constant $\epsilon>0$, we give an $\exp(\tilde{O}(\sqrt{n}))$-time algorithm for the $1$ vs $1-\epsilon$ Best Separable State (BSS) problem of distinguishing, given an $n^2\times n^2$ matrix $M$ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state $\rho$ that $M$ accepts with probability $1$, ... more >>>

TR17-010 | 18th January 2017
Xiaodi Wu, Penghui Yao, Henry Yuen

#### Raz-McKenzie simulation with the inner product gadget

In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions $f$ composed with the Inner Product gadget $g_{IP}(x,y) = \sum_i x_iy_i \mathrm{mod} \, 2$ of logarithmic size. In other words, given a function \$f: ... more >>>

TR17-009 | 19th January 2017
Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

#### Towards an algebraic natural proofs barrier via polynomial identity testing

We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich ... more >>>

-> Older reports

ISSN 1433-8092 | Imprint