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.

Fixed Minor Typos

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.

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

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.

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.

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.