Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [ac0]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
123 views

$\mathrm{AC}^0$ upper bound for Hamming weight

Consider Theorem 11 of this paper (S. Aaronson, BQP and the Polynomial Hierarchy), which says: Any depth $d$ circuit that accepts all $n$ bit strings of Hamming weight $\frac{n}{2} + 1$ and rejects ...
AngryLion's user avatar
  • 173
6 votes
0 answers
153 views

$\mathbf{AC}^0$ lower bounds for $\mathsf{Gap}\text{-}\mathsf{Max3SAT}$

Various gapped maximization problems are known not to be $\mathbf{NP}$-hard under $\mathbf{AC}^0$ reductions, e.g., $\mathsf{Gap}_{1,\epsilon}\text{-}\mathsf{Max3SAT}$ (see, e.g., Proposition 4 of ...
Noah Singer's user avatar
3 votes
1 answer
135 views

What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?

It is known $AC^0[2]$ cannot get majority function. Is there a literature on simulation of $MAJ$ function utilizing $AC^0[2,3,\dots,p]$ gates for a finite fixed set of primes $2$ to $p=O(1)$? What is ...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
135 views

$\mathit{FO}[+,\times]$ seems more powerful than $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$?

I’ve been reading up on the connection between first order logic and small circuit complexity classes, and specifically Barrington, Immerman, and Straubing’s paper “On Uniformity Within $\mathit{NC}^1$...
Jake's user avatar
  • 1,214
8 votes
0 answers
468 views

How many different proofs are there of parity is not in AC0?

The theorem that Parity is not in $\mathsf{AC}^0$ is one of the gemstones of complexity theory. I wonder how many different proofs there are of this result? What constitutes "different" is also a part ...
Goose's user avatar
  • 81
5 votes
0 answers
165 views

The evaluation problem for AC$^0_d$ formulas is in FO

Let $d \in \mathbb{N}$ be arbitrary. Let $\mathsf{AC^0_d}$-Eval be the following promise problem: Input: A depth $d$ formula $\varphi(x)$ and a binary string $a$. Output: $\varphi(a)$ I am looking for ...
Kaveh's user avatar
  • 21.7k
11 votes
1 answer
591 views

For what c is division by c in AC0?

Suppose that our input is a binary $x$ and we have to output $\lfloor x/c \rfloor$, where $c$ is some constant integer. This is just a shift if $c$ is a power of two, but what about other numbers? Can ...
domotorp's user avatar
  • 14k
15 votes
1 answer
305 views

Does ${\bf AC^0PAD} = {\bf PPAD}$?

What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a logspace Turing-machine or an ${\bf AC^0}$ circuit encodes the problem? Recently giving ...
domotorp's user avatar
  • 14k