Change search
ReferencesLink to record
Permanent link

Direct link
On the correlation of parity and small-depth circuits
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
2014 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 43, no 5, 1699-1708 p.Article in journal (Refereed) Published
Abstract [en]

We prove that the correlation of a depth-d unbounded fanin circuit of size S with parity of n variables is at most 2(-Omega(n/(log S)d-1)).

Place, publisher, year, edition, pages
2014. Vol. 43, no 5, 1699-1708 p.
Keyword [en]
circuits complexity, small-depth circuits, parity, switching lemma
National Category
Computer and Information Science Mathematics
URN: urn:nbn:se:kth:diva-157580DOI: 10.1137/120897432ISI: 000344753500007ScopusID: 2-s2.0-84911904342OAI: diva2:771197
EU, European Research Council, 226 203

QC 20141212

Available from: 2014-12-12 Created: 2014-12-11 Last updated: 2014-12-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Theoretical Computer Science, TCS
In the same journal
SIAM journal on computing (Print)
Computer and Information ScienceMathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 66 hits
ReferencesLink to record
Permanent link

Direct link