16

I have learned from talking to Ryan Williams (who deserves the credit for my being able to post this answer) that it is known from Paul and Pippenger that Circuit Eval can be decided by a quasilinear time multitape TM and also that there are reductions from multitape TMs to circuits which give only a quasilinear size blowup. That is, Circuit Eval has ...


13

$\def\N{\mathbb N}\DeclareMathOperator\sym{Sym}\def\cC{\mathcal C}\def\cD{\mathcal D}\def\cP{\mathcal P}\def\cI{\mathcal W}\def\cMI{\mathcal{MW}}\DeclareMathOperator\pol{Pol}\DeclareMathOperator\inv{Inv}\DeclareMathOperator\minv{MInv}\let\pres\parallel$This is a presentation of one half of a duality for reversible transformations, analogous to the standard ...


11

The circuit complexity of any boolean function of $n$ variables is at most $(1+o(1))2^n/n$, so a separation of between circuit and formula complexity of $\Omega(2^n)$ is not possible. This upper bound was established by Lupanov, and his method is known as the Lupanov representation of boolean functions. It also gives an upper bound of $(1+o(1))2^n/\log n$ ...


9

Kaveh's answer provides an answer do the question as you have stated it (and this is the usual proof for showing that $\mathsf{TC}^0$ is contained in $\mathsf{NC}^1$). But I was thinking that you might actually have intended to ask a slightly a different question. Namely for an explicit polynomial size monotone formula for majority. Since majority is ...


9

Computing restricted threshold gate ($\sum_i x_i \geq k$) is essentially sorting input bits. If you can sort the bits then it is easy to compare the result to $k$ and compute restricted threshold. On the other hand, assume that we have an circuits to compute restricted threshold. We can do a parallel search to find the number of ones in the input and ...


7

No, there is no decomposition of the entire family $\{F_{2^n}\}_{n\geqslant1}$ into a single finite gate-set. Here's why. The QFTs involve only coefficients over $\overline{\mathbb Q}$, the complex algebraic closure of the rational numbers. In analogy to [Adleman+Demarrais+Huang–1997], if we involved any gates which included any transcendental numbers,...


7

The proof (due to Miller and Preparata, 1975) that any symmetric function can be computed by circuits over {AND,OR,NOT} in logarithmic depth can be found, e.g., in Complexity of Boolean Functions by Ingo Wegener (Theorem 4.1, page 76). The corresponding circuit has linear size. And since the depth is logarithmic it can be turned to a formula of polynomial ...


3

This problem with $k=3$ is coNP-hard (and therefore coNP-complete). To prove this, I will reduce from 3-SAT to the complement of this problem (for a given $NC_3^0$ circuit, does the circuit enact a non-bijective function). First a preliminary definition that will be helpful: We define a labeled graph to be a directed graph, some of whose edges are labeled ...


2

In the same paper that shows the $n^{1.5}$ lower bound for depth-2 (Daniel Kane and me) we also show that a random function is extremely likely to have depth 2 threshold circuit complexity at least $$2^n/n^3$$. So the answer to question 2 is "yes" Since random functions need large threshold circuits, question 1 seems to be effectively asking "does $P \neq ...


2

There's the Minsky-Papert function, which is a depth-two formula, OR composed with AND, where the OR is of size $n^{1/3}$ and the AND is of size $n^{2/3}$. I.e., it's $OR_{n^{1/3}}\circ AND_{n^{2/3}}$. Then there's the particular communication complexity problem studied in the papers you linked, which is now a function of 2 $n$-bit strings $x$ and $y$, ...


2

First of all: your definition of $WCS[C_{t,d}]$ does not match the usual one. The common definition asks for a satisfying assignment of Hamming weight exactly $k$, rather than at most $k$, and this can make an important difference. However, regardless of whether you want at most, or exactly, Hamming weight $k$, the weighted circuit-sat problem for constant-...


2

The circuit characterization are by Kannan, Venkateswaran, Vinay, and Yao given in the paper: A Circuit-Based Proof of Toda′s Theorem


Only top voted, non community-wiki answers of a minimum length are eligible