WEBSITE > HOME:

#### What we do and why

The Electronic Colloquium on Computational Complexity is a new 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 profile and
• strictly mathematical format.

#### Central topics

• models of computation and their complexity,
• complexity bounds (with the emphasis on lower bounds).
Specific areas including complexity issues are
• combinatorics,
• communication complexity,
• cryptography,
• combinatorial optimization,
• complexity of learning algorithms,
• logic.

Here are some papers on the idea and concept of electronic colloquia and ECCC.
6th March 2012 12:04

#### ECCC Archive DVD 2011

In 2011 we had a total count of 174 published reports on ECCC. The collection of all the reports from 2011 is now available on DVD. You can order the archive (and also the archive DVDs from earlier years) at the local office. Please email to eccc@eccc.hpi-web.de for ordering.

9th March 2011 09:41

#### ECCC Archive DVD 2010

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

8th April 2010 10:10

With the extension of our scientific board and the implementation of the improved screening mechanism incorporating topics of interest already in the submission process, the ECCC can now provide a clarified Call for Papers.
Please keep in mind, that the ECCC focusses on complexity issues rather than on general algorithmic topics. If you plan to submit, please verify that your work matches the scope of interest defined in the CfP.

-> Older news
TR13-173 | 28th November 2013
Anindya De, Rocco Servedio

#### Efficient deterministic approximate counting for low degree polynomial threshold functions

We give a deterministic algorithm for
approximately counting satisfying assignments of a degree-$d$ polynomial threshold function
(PTF).
Given a degree-$d$ input polynomial $p(x_1,\dots,x_n)$ over $\mathbb{R}^n$
and a parameter $\epsilon > 0$, our algorithm approximates
$\mathbf{P}_{x \sim \{-1,1\}^n}[p(x) \geq 0]$
to within an additive $\pm \epsilon$ in time $O_{d,\epsilon}(1)\cdot ... more >>> TR13-172 | 1st December 2013 Anindya De, Ilias Diakonikolas, Rocco Servedio #### Deterministic Approximate Counting for Degree-$2$Polynomial Threshold Functions We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-$2$polynomial threshold function. Given a degree-2 input polynomial$p(x_1,\dots,x_n)$and a parameter$\eps > 0$, the algorithm approximates $\Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0]$ to within an additive$\pm \eps$in ... more >>> TR13-171 | 1st December 2013 Anindya De, Ilias Diakonikolas, Rocco Servedio #### Deterministic Approximate Counting for Juntas of Degree-$2$Polynomial Threshold Functions Let$g: \{-1,1\}^k \to \{-1,1\}$be any Boolean function and$q_1,\dots,q_k$be any degree-2 polynomials over$\{-1,1\}^n.$We give a \emph{deterministic} algorithm which, given as input explicit descriptions of$g,q_1,\dots,q_k$and an accuracy parameter$\eps>0$, approximates $\Pr_{x \sim \{-1,1\}^n}[g(\sign(q_1(x)),\dots,\sign(q_k(x)))=1]$ to within an additive$\pm \eps\$. For any constant ... more >>>

-> Older reports

ISSN 1433-8092 | Imprint