Search Results

Results tagged with
Search options user 40
14 results

Circuit complexity is the study of resource-bounded circuits and the functions computed by such circuits.

Regarding the choice of basis: all finite bases are (polynomially) equivalent. That means that if $C$ is a circuit over a finite base $B$ and $B'$ is any complete basis, then there is an equivalent ci …
answered Jan 24 '14 by Yuval Filmus
Your question is related to the well-known question about computing the minimum and maximum of a list simultaneously using the minimum number of comparisons. In that case the answer is $3\lfloor n/2 \ … answered Dec 3 '11 by Yuval Filmus More generally, you can consider the identity $$f(g(x)) = g^{(n)}(x),$$ which generalizes your identities, in which$n=3,1,2$(respectively). For a given function$g$, this identity states that$f$… answered Mar 27 '14 by Yuval Filmus Suppose you have$n$numbers$x_1,\ldots,x_n$of width$m \geq \log n$. Without loss of generality, all numbers are different (add an extra$\log n$lower-order bits). Two numbers can be compared in A … answered Oct 17 '12 by Yuval Filmus Here's a simplification of Ryan's answer. Suppose that$\Lambda \in NE \setminus E$. Define the language$L = \{x : |x| \in \Lambda\}$. The assumption$\Lambda \in NE \setminus E$translates to$L \in …
answered Oct 6 '10 by Yuval Filmus
You can use the usual switching lemma argument. You haven't explained how you represent your input in binary, but under any reasonable encoding, the following function is AC$^0$-equivalent to your fun …
answered Oct 31 '13 by Yuval Filmus
Every function $\mathbb{F}_p^n \longrightarrow \mathbb{F}_p$ (where $p$ is prime) can be written as a polynomial. For the proof, consider all $p^n$ monomials, and show that they are linearly independe …
answered May 6 '12 by Yuval Filmus
Raz and McKenzie, in Separation of the monotone NC hierarchy, show that the monotone NC hierarchy is strict, and separate monotone NC from monotone P.
answered Oct 10 '12 by Yuval Filmus
See also the recent paper of Daniel Kane and Ryan Williams, Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-2 and Depth-3 Threshold Circuits (STOC 2016). Ryan describes the paper as …
answered May 2 '16 by Yuval Filmus
The other two "classical" methods are Haken's bottleneck method and Karchmer's fusion method (so named by Avi Wigderson), both much easier to apply in the monotone setting.
answered Nov 20 '10 by Yuval Filmus
No. Consider the following function on $\{0,1\}^n$: $$f(x) = x_0 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1}).$$ Clearly this function is hard for AC0. On …
answered Sep 29 '12 by Yuval Filmus
Let $f\colon \{0,1\}^n \to \{0,1\}$, and let $g\colon \{0,1\}^n \to \{0,1\}$ be chosen uniformly. Then $\Pr[f=g] \sim 2^{-n}\mathrm{Bin}(2^n,1/2)$, and so a Chernoff bound shows that  \Pr_g[\Pr[f=g] …
answered Aug 29 '17 by Yuval Filmus
The same distinction exists in circuit complexity: tree-like circuits are known as formulas, and it is easier to prove lower bounds for them. For example, there are no superlinear lower bounds for cir …
answered Jan 24 '14 by Yuval Filmus
Here is an even simpler problematic situation. Let $A(k)$ be the first string (in lexicographic order) such that $K(A(k)) \geq k$; such a string provably exists for all $k$. Then $K(A(k)) \geq k$. Th …
answered Jul 20 '12 by Yuval Filmus