Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Code code:"if (foo != bar)"
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Bookmarks inbookmarks:mine
inbookmarks:1234
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with
Search options user 40

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

5
votes
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
3
votes
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
6
votes
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
9
votes
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
32
votes
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
7
votes
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
2
votes
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
7
votes
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
6
votes
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
8
votes
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
19
votes
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
4
votes
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
7
votes
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
1
vote
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