English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This special issue contains full versions of three papers that were presented at the 21st Annual IEEE Computational Complexity Conference (CCC 2006), held in Prague during July 16–20, 2006. These papers were invited by the conference program committee, chaired by Manindra Agrawal. All submitted papers were then subject to the normal refereeing process of this journal. The first paper of this issue is Polynomial Identity Testing for Depth 3 Circuits by Neeraj Kayal and Nitin Saxena. It gives a deterministic polynomialtime algorithm for testing if a given arithmetic circuit of depth 3, with constant top fan-in, computes an identically zero polynomial. This is currently the best derandomization result for a special case of Polynomial Identity Testing, one of the central problems in BPP that is not known to be in P . This paper received both the best paper and best student paper awards at the conference. The next paper, A Generic Time Hierarchy With One Bit of Advice by Dieter van Melkebeek and Konstantin Pervyshev, addresses a classical question of time hierarchy. For a number of semantic complexity classes (such as BPP , ZPP , AM , etc.) with a small amount of advice, the authors show that in more time one can decide more languages. The final paper of this issue, Every linear threshold function has a lowweight approximator by Rocco Servedio, proves a tight result showing that every given linear threshold function can be well approximated by another linear threshold function with small integer weights. This has applications to approximate counting and computational learning theory. Further papers were selected and will appear in later issues of this journal. We want to thank the authors of these papers for submitting them to the special issue and revising them within a short time frame, and the referees who helped us immensely with their thorough and timely reviews. We also thank the PC Chair Manindra Agrawal and Editor-in-Chief Joachim von zur Gathen for inviting us to edit this special issue!

Special Issue “Conference on Computational Complexity 2006” Guest Editors’ Foreword