Standard

Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. / Kulikov, Alexander S.; Podolskii, Vladimir V.

In: Theory of Computing Systems, Vol. 63, No. 5, 07.2019, p. 956-986.

Research output: Contribution to journal › Article › peer-review

Harvard

Kulikov, AS & Podolskii, VV 2019, 'Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates', Theory of Computing Systems, vol. 63, no. 5, pp. 956-986. https://doi.org/10.1007/s00224-018-9900-3

APA

Kulikov, A. S., & Podolskii, V. V. (2019). Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. Theory of Computing Systems, 63(5), 956-986. https://doi.org/10.1007/s00224-018-9900-3

Vancouver

Kulikov AS, Podolskii VV. Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. Theory of Computing Systems. 2019 Jul;63(5):956-986. https://doi.org/10.1007/s00224-018-9900-3

Author

Kulikov, Alexander S. ; Podolskii, Vladimir V. / Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. In: Theory of Computing Systems. 2019 ; Vol. 63, No. 5. pp. 956-986.

BibTeX

@article{9b06f85fa0324ed9b5dda98aae16da26,
title = "Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates",
abstract = "We study the following computational problem: for which values of k, the majority of n bits MAJn can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJk ∘ MAJk. We observe that the minimum value of k for which there exists a MAJk ∘ MAJk circuit that has high correlation with the majority of n bits is equal to Θ(n1/2). We then show that for a randomized MAJk ∘ MAJk circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n2/3 + o(1). We show a worst case lower bound: if a MAJk ∘ MAJk circuit computes the majority of n bits correctly on all inputs, then k ≥ n13/19 + o(1).",
keywords = "Average case, Circuit complexity, Constant depth, Correlation, Majority, Threshold, Worst case",
author = "Kulikov, {Alexander S.} and Podolskii, {Vladimir V.}",
note = "Kulikov, A.S. & Podolskii, V.V. Theory Comput Syst (2019) 63: 956. https://doi.org/10.1007/s00224-018-9900-3",
year = "2019",
month = jul,
doi = "10.1007/s00224-018-9900-3",
language = "English",
volume = "63",
pages = "956--986",
journal = "Theory of Computing Systems",
issn = "1432-4350",
publisher = "Springer Nature",
number = "5",

}

RIS

TY - JOUR

T1 - Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

AU - Kulikov, Alexander S.

AU - Podolskii, Vladimir V.

N1 - Kulikov, A.S. & Podolskii, V.V. Theory Comput Syst (2019) 63: 956. https://doi.org/10.1007/s00224-018-9900-3

PY - 2019/7

Y1 - 2019/7

N2 - We study the following computational problem: for which values of k, the majority of n bits MAJn can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJk ∘ MAJk. We observe that the minimum value of k for which there exists a MAJk ∘ MAJk circuit that has high correlation with the majority of n bits is equal to Θ(n1/2). We then show that for a randomized MAJk ∘ MAJk circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n2/3 + o(1). We show a worst case lower bound: if a MAJk ∘ MAJk circuit computes the majority of n bits correctly on all inputs, then k ≥ n13/19 + o(1).

AB - We study the following computational problem: for which values of k, the majority of n bits MAJn can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJk ∘ MAJk. We observe that the minimum value of k for which there exists a MAJk ∘ MAJk circuit that has high correlation with the majority of n bits is equal to Θ(n1/2). We then show that for a randomized MAJk ∘ MAJk circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n2/3 + o(1). We show a worst case lower bound: if a MAJk ∘ MAJk circuit computes the majority of n bits correctly on all inputs, then k ≥ n13/19 + o(1).

KW - Average case

KW - Circuit complexity

KW - Constant depth

KW - Correlation

KW - Majority

KW - Threshold

KW - Worst case

UR - http://www.scopus.com/inward/record.url?scp=85057615793&partnerID=8YFLogxK

U2 - 10.1007/s00224-018-9900-3

DO - 10.1007/s00224-018-9900-3

M3 - Article

AN - SCOPUS:85057615793

VL - 63

SP - 956

EP - 986

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 5

ER -

ID: 49820484