  Under the auspices of the Computational Complexity Foundation (CCF)     REPORTS > DETAIL:

Revision(s):

Revision #3 to TR20-122 | 1st October 2020 00:42

Size Bounds on Low Depth Circuits for Promise Majority Revision #3
Authors: Joshua Cook
Accepted on: 1st October 2020 00:42
Keywords:

Abstract:

We give two results on the size of AC0 circuits computing promise majority. $\epsilon$-promise majority is majority promised that either at most an $\epsilon$ fraction of the input bits are 1 or at most $\epsilon$ are 0.

First, we show super-quadratic lower bounds on both monotone and general depth-3 circuits for promise majority.

For any $\epsilon \in (0, 1/2)$, monotone depth-3 AC0 circuits for $\epsilon$-promise majority have size
$\tilde{\Omega}\left(\epsilon^3 n^{2 + \frac{\ln(1 - \epsilon)}{\ln(\epsilon)}}\right)$

For any $\epsilon \in (0, 1/2)$, general depth-3 AC0 circuits for $\epsilon$-promise majority have size
$\tilde{\Omega}\left(\epsilon^3 n^{2 + \frac{\ln(1 - \epsilon^2)}{2\ln(\epsilon)}}\right)$

These are the first quadratic size lower bounds for depth-3 $\epsilon$-promise majority circuits for $\epsilon < 0.49$.

Second, we give both uniform and non-uniform sub-quadratic size constant-depth circuits for promise majority.

For integer $k \geq 1$ and constant $\epsilon \in (0, 1/2)$, there exists monotone \emph{non} uniform AC0 circuits of depth-$(2 + 2 k)$ computing $\epsilon$-promise majority with size
$\tilde{O}\left(n^{\frac{1}{1 - 2^{-k}}}\right)$

For integer $k \geq 1$ and constant $\epsilon \in (0, 1/2)$, there exists monotone \emph{uniform} AC0 circuit of depth-$(2 + 2 k)$ computing $\epsilon$-promise majority with size
$n^{\frac{1}{1 - \left(\frac{2}{3}\right)^k} + o(1)}$

These circuits are based on incremental improvements to existing depth-3 circuits for promise majority given by Ajtai and Viola combined with a divide and conquer strategy.

Changes to previous version:

Fixed Minor Typos

Revision #2 to TR20-122 | 27th September 2020 00:48

Size Bounds on Low Depth Circuits for Promise Majority

Revision #2
Authors: Joshua Cook
Accepted on: 27th September 2020 00:48
Keywords:

Abstract:

We give two results on the size of AC0 circuits computing promise majority. $\epsilon$-promise majority is majority promised that either at most an $\epsilon$ fraction of the input bits are 1 or at most $\epsilon$ are 0.

First, we show super-quadratic lower bounds on both monotone and general depth-3 circuits for promise majority.

For any $\epsilon \in (0, 1/2)$, monotone depth-3 AC0 circuits for $\epsilon$-promise majority have size
$\tilde{\Omega}\left(\epsilon^3 n^{2 + \frac{\ln(1 - \epsilon)}{\ln(\epsilon)}}\right)$

For any $\epsilon \in (0, 1/2)$, general depth-3 AC0 circuits for $\epsilon$-promise majority have size
$\tilde{\Omega}\left(\epsilon^3 n^{2 + \frac{\ln(1 - \epsilon^2)}{2\ln(\epsilon)}}\right)$

These are the first quadratic size lower bounds for depth-3 $\epsilon$-promise majority circuits for $\epsilon < 0.49$.

Second, we give both uniform and non-uniform sub-quadratic size constant-depth circuits for promise majority.

For integer $k \geq 1$ and constant $\epsilon \in (0, 1/2)$, there exists monotone \emph{non} uniform AC0 circuits of depth-$(2 + 2 k)$ computing $\epsilon$-promise majority with size
$\tilde{O}\left(n^{\frac{1}{1 - 2^{-k}}}\right)$

For integer $k \geq 1$ and constant $\epsilon \in (0, 1/2)$, there exists monotone \emph{uniform} AC0 circuit of depth-$(2 + 2 k)$ computing $\epsilon$-promise majority with size
$n^{\frac{1}{1 - \left(\frac{2}{3}\right)^k} + o(1)}$

These circuits are based on incremental improvements to existing depth-3 circuits for promise majority given by Ajtai and Viola combined with a divide and conquer strategy.

Changes to previous version:

Accidentally used Jaikumar Radhakrishnan first name instead of his last, minor typos.

Revision #1 to TR20-122 | 26th September 2020 08:30

Size Bounds on Low Depth Circuits for Promise Majority

Revision #1
Authors: Joshua Cook
Accepted on: 26th September 2020 08:31
Keywords:

Abstract:

We give two results on the size of AC0 circuits computing promise majority. $\epsilon$-promise majority is majority promised that either at most an $\epsilon$ fraction of the input bits are 1 or at most $\epsilon$ are 0.

First, we show super-quadratic size lower bounds on both monotone and general depth-3 circuits for promise majority.

For any $\epsilon \in (0, 1/2)$, monotone depth-3 AC0 circuits for $\epsilon$-promise majority have size
$tilde{\Omega}\left(\epsilon^3 n^{2 + \frac{\ln(1 - \epsilon)}{\ln(\epsilon)}}\right).$

For any $\epsilon \in (0, 1/2)$, general depth-3 AC0 circuits for $\epsilon$-promise majority have size
$\tilde{\Omega}\left(\epsilon^3 n^{2 + \frac{\ln(1 - \epsilon^2)}{2\ln(\epsilon)}}\right).$

These are the first quadratic size lower bounds for depth-3 $\epsilon$-promise majority circuits for $\epsilon < 0.49$.

Second, we give both uniform and non-uniform sub-quadratic size constant-depth circuits for promise majority.

For integer $k \geq 1$ and constant $\epsilon \in (0, 1/2)$, there exists monotone \emph{non} uniform AC0 circuits of depth-$(2 + 2 k)$ computing $\epsilon$-promise majority with size
$\tilde{O}\left(n^{\frac{1}{1 - 2^{-k}}}\right).$

For integer $k \geq 1$ and constant $\epsilon \in (0, 1/2)$, there exists monotone \emph{uniform} AC0 circuit of depth-$(2 + 2 k)$ computing $\epsilon$-promise majority with size
$n^{\frac{1}{1 - \left(\frac{2}{3}\right)^k} + o(1)}.$

These circuits are based on incremental improvements to existing depth-3 circuits for promise majority given by Ajtai and Viola combined with a divide and conquer strategy.

Changes to previous version:

Fixed formatting issues.
Added a related work by Chaudhuri and Jaikumar from 96: "Deterministic Restrictions in Circuit Complexity".
Reworded the motivations to be more clear.
Updated the open problems.
Fixed many typos, grammatical mistakes, and minor errors.

Paper:

TR20-122 | 8th August 2020 07:01

Size Bounds on Low Depth Circuits for Promise Majority

TR20-122
Authors: Joshua Cook
Publication: 16th August 2020 17:37
Keywords:

Abstract:

We give two results on the size of AC0 circuits computing promise majority. $\epsilon$-promise majority is majority promised that either at most an $\epsilon$ fraction of the input bits are 1, or at most $\epsilon$ are 0.

First, we show super quadratic lower bounds on both monotone and general depth 3 circuits for promise majority.

For any $\epsilon \in (0, 1/2)$, monotone depth 3 AC0 circuits for $\epsilon$-promise majority have size
$\tilde{\Omega}\left(\epsilon^3 n^{2 + \frac{\ln(1 - \epsilon)}{\ln(\epsilon)}}\right)$

For any $\epsilon \in (0, 1/2)$, general depth 3 AC0 circuits for $\epsilon$-promise majority have size
$\tilde{\Omega}\left(\epsilon^3 n^{2 + \frac{\ln(1 - \epsilon^2)}{2\ln(\epsilon)}}\right)$

These are the first nontrivial size lower bounds on depth 3 promise majority circuits for $\epsilon < 0.45$.

Second, we give both uniform and non-uniform sub-quadratic size constant depth circuits for promise majority.

For integer $k \geq 1$, constant $\epsilon \in (0, 1/2)$, there exists monotone non uniform AC0 circuits of depth $2 + 2 \cdot k$ computing $\epsilon$-promise majority with size
$\tilde{O}\left(n^{\frac{1}{1 - 2^{-k}}}\right)$

For integer $k \geq 1$, constant $\epsilon \in (0, 1/2)$, there exists monotone uniform AC0 circuit of depth $2 + 2 \cdot k$ computing $\epsilon$-promise majority with size
$n^{\frac{1}{1 - \left(\frac{2}{3}\right)^k} + o(1)}$

These circuits are based on incremental improvements to existing depth 3 circuits for promise majority given by Ajtai and Viola combined with a divide and conquer strategy.

ISSN 1433-8092 | Imprint