Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
An Average-case Depth Hierarchy Theorem for Higher Depths
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
2016 (English)In: 2016 IEEE 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2016, Vol. 2016, p. 79-88Conference paper, Published paper (Refereed)
Abstract [en]

We extend the recent hierarchy results of Ross-man, Servedio and Tan [1] to address circuits of almost logarithmic depth. Our proof uses the same basic approach as [1] but a number of small differences enables us to obtain a stronger result by a significantly shorter proof.

Place, publisher, year, edition, pages
IEEE Computer Society, 2016. Vol. 2016, p. 79-88
Series
Annual IEEE Symposium on Foundations of Computer Science, ISSN 0272-5428 ; 2016
Keywords [en]
small-depth circuits, average case complexity, circuit complexity, hierarchy theorems
National Category
Other Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-200425DOI: 10.1109/FOCS.2016.18ISI: 000391198500009Scopus ID: 2-s2.0-85009357333ISBN: 978-1-5090-3933-3 (print)OAI: oai:DiVA.org:kth-200425DiVA, id: diva2:1069838
Conference
57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016, New Brunswick, United States, 9 October 2016 through 11 October 2016
Note

QC 20170130

Available from: 2017-01-30 Created: 2017-01-27 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Theoretical Computer Science, TCS
Other Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 22 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf