29
Hardness
Following your comment on the question, we will call a circuit where each output bit depends on at most k input bits a “NC0k circuit.” Using this term, your problem is coNP-complete in case of NC05 circuits. That is, the following problem is coNP-complete.
Instance: A Boolean circuit C with n input bits and n output bits where each output bit ...
25
@Suresh: following your advice, here is my "answer". The status of circuit lower bounds is quite depressing. Here are the "current records":
$4n-4$ for circuits over $\{\land,\lor,\neg\}$, and $7n-7$
for circuits over $\{\land,\neg\}$ and $\{\lor,\neg\}$
computing $\oplus_n(x)=x_1\oplus x_2\oplus\cdots\oplus x_n$;
Redkin (1973). These bounds are tight.
...
25
Lower bounds for monotone arithmetic circuits come easier because they forbid cancellations. On the other hand, we can prove exponential lower bounds for circuits computing boolean functions even if any monotone real-valued functions $g:R\times R\to R$ are allowed as gates (see e.g. Sect. 9.6 in the book).
Even though monotone arithmetic circuits are weaker ...
25
I don't think the paper in the other answer contains an answer to your question. Indeed I am not really sure a proof has been published, because the result follows from other well known results.
The proof of the statement you want is as follows:
$\Sigma_3 E$ contains a function of maximum possible circuit complexity on every input length, by simply ...
24
[Following a suggestion of Kaveh, I am putting my (somewhat extended) comment as an answer]
This "conjecture" of Kolmogorov is just a rumor. It was not published anywhere. In the former USSR, "publishing" mathematics meant something different than what it does today: give a talk at a seminar or tell your colleagues at lunch. Counting papers was not an issue....
23
If I don't misunderstand what you mean by AND&OR gate, it is basically a comparator gate which takes two input bits $x$ and $y$ and produces two output bits $x\wedge y$ and $x\vee y$. The two output bits $x\wedge y$ and $x\vee y$ are basically min$(x,y)$ and max$(x,y)$.
Comparator circuits are built by composing these comparator gates together but ...
23
The following paper seems to contain an answer:
Mix Barrington, D. A., Compton, K., Straubing, H., Therien, D.: Regular languages in $\mathsf{NC}^1$. Journal of Computer and System Sciences 44(3), 478-499 (1992) (link)
One of the characterizations obtained there is as follows. The class $\mathsf{REG} \cap \mathsf{AC}^0 \subset \{0, 1\}^*$ contains exactly ...
22
Consider a fanin 2 circuit of $C$ depth $O(\log n)$. Divide the layers of $C$ into $O(\log n/\log\log n)$ blocks each of $\log\log n$ consecutive layers. We now wish to replace each block by a depth 2 circuit. Namely, each gate in the last layer of a block depends on at most $2^{\log\log n} = \log n$ gates of the last layer in the block below. We can thus ...
answered Oct 9 '12 at 9:26
Kristoffer Arnsfelt Hansen
3,8962 gold badges22 silver badges34 bronze badges
22
The footnote of my paper that you cite refers to a heuristic "argument" as well, at least, what we think was Kolmogorov's intuition -- the positive resolution of Hilbert's thirteenth problem.
http://en.wikipedia.org/wiki/Hilbert's_thirteenth_problem
In particular, it was proved by Kolmogorov and Arnold that any continuous function on $n$ variables can be ...
21
Markov proved that any function of $n$ inputs can be computed with only $\lceil \log (n+1)\rceil$ negations. An efficient constructive version was described by Fisher. See also an exposition of the result from the GLL blog.
More precisely:
Theorem: Suppose $f : \{0,1\}^n \to \{0,1\}^m$ is computed by a circuit $C$ with $g$ gates, then it is also computed ...
20
No, the unavoidability of constructivity definitely still leaves GCT open as a viable plan of attack on lower bound problems such as $NP$ vs. $P/poly$.
First, it is worth mentioning that Ryan's result on constructivity is very similar in flavor to the so-called "Flip Theorems" by Mulmuley, which say, for example, that if permanent does not have poly-size ...
19
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 the other hand, the function is almost constant, so almost all of its Fourier spectrum is on the first level.
If you want a balanced counterexample, consider
$$...
18
According to the paper A $5n − o(n)$ Lower Bound on the Circuit Size over $U_2$ of a Linear Boolean Function by Kulikov, Melanich, and Mihajlin, when $m=o(n)$ there are no lower bounds known better than $3n - o(n)$. It also outlines a method for obtaining functions for which a $4n - o(n)$ lower bound holds, when $m=n$, based on a result of Lamagne and ...
answered Mar 6 '14 at 14:58
Kristoffer Arnsfelt Hansen
3,8962 gold badges22 silver badges34 bronze badges
18
This is NP-hard. See:
Joan Boyar, Philip Matthews, René Peralta. Logic Minimization Techniques with Applications to Cryptology. http://link.springer.com/article/10.1007/s00145-012-9124-7
The reduction is from Vertex Cover and is very nice.
Given a graph $(\{1,\ldots,n\},E)$ with $m=|E|$, define an $m \times (n+1)$ matrix $A$ as: $A[i,j] = 1$ if $j < n+...
17
This question has been completely resolved (up to constant factors) by a recent result of Benjamin Rossman (http://eccc.hpi-web.de/report/2013/169/).
As Kaveh points out above, a depth $d$, size $S$, circuit can be converted to a depth $d$, size $S^d$ formula.
Rossman shows that this is essentially tight. For any depth $d$, he exhibits a function that can ...
17
You're really asking two different questions and hoping that there is a single response which answers both: (1) What natural notions of quantum monotone circuits are there? (2) What would a lattice-based Razborov-style quantum result look like?
It isn't obvious how to achieve both at the same time, so I'll describe what to me seems a reasonable notion of ...
17
Let me first correct a possible misunderstanding: unfortunately we don't know yet that $NEXP \not\subset TC^0$. My most recent lower bound is $NEXP \cap coNEXP \not\subset ACC$.
Now, the answer to your question is no. It is still very possible that techniques based on GCT can separate $P$ from $NP$.
A few more comments about this: the relation between ...
17
It's common to say that $f$ and $g$ commute with respect to composition (where the property is known as commutativity). See, e.g., http://en.wikipedia.org/wiki/Function_composition.
16
I might miss something, but isn't $AC^0_{bf}$ the same as a Formula? Since every input bit can have an effect on at most a bounded number of gates, we can simply suppose that every gate has only one output (after possibly duplicating a few things) and we can push down not gates as well. We know that the formula size of parity is n^2 (see Troy J. Lee, "The ...
16
Let $v_0, v_1, \ldots, v_n \in \mathbb{Z}_2^m$. The problem is to determine whether the following system has a solution:
$$
\begin{pmatrix}
v_1 & \cdots & v_n
\end{pmatrix}
\begin{pmatrix}
x_1 \\
\vdots \\
x_n
\end{pmatrix}
=
v_0 \, (\text{mod } 2)
$$
This problem is known to be $\oplus L$-complete by [Damm90, BDHM92], thus inside $\text{...
16
The paper called Multiplication by a constant is sublinear (PDF) gives an algorithm for $\mathcal{O}\left(\frac{n}{\log n}\right)$ shift/addition operations, where $n$ is the size of the constant.
Essentially, it works by looking for the $1$-bits in the constant, shifting and adding the number to be multiplied only for those $1$ bits in the constant (like ...
16
On techniques for proving poly-log circuit-depth lower bounds, all current approaches work under restricted settings.
Like, in the work leading to GCT that you mention, the lower bound applies to a restricted PRAM model without bit operations.
Under another restriction, which is the monotone restriction for monotone boolean functions, there is a Fourier-...
16
Check Chapter 7 of Salil Vadhan's monograph. Corollary 7.64 is Impagliazzo and Wigderson's result.
16
Recently, I proved that s(f) = bs(f) for unate functions and read-once functions over the Boolean operators AND, OR and EXOR, and my paper including the results was accepted to TCS 2014.
(http://dx.doi.org/10.1007/978-3-662-44602-7_9)
You may be attacking this problem. If so, I feel sorry, but I started to attack the problem independently before the ...
16
The answer is “yes” if $t=n^{O(1)}$. More generally, a threshold $\{+,\cdot\}$-circuit of size $s$ with threshold $t$ can be simulated by a $\{\lor,\land\}$-circuit of size $O(t^2s)$.
First, observe that it is enough to evaluate the circuit in $\{0,\dots,t\}$ with truncated addition and multiplication: in particular, if $a,a'\ge t$, then $a+b,a'+b\ge t$, ...
16
Addition and subtraction of binary numbers are in $\mathsf{AC^0}$.
For any constant number $c$,
$x \bmod c$ is $\mathsf{AC^0}$ reducible to division by $c$ ($\lfloor x/c \rfloor$):
$$x \bmod c = x -
(\overbrace{\lfloor x/c \rfloor + \cdots + \lfloor x/c \rfloor}^{c \text{ times}}) $$
It is known that $x \bmod c$ is hard for $\mathsf{AC^0}$ for any $c$
...
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 ...
16
Not sure how much of an answer this is, I'm just indulging in some rumination.
Question 1 could be equally asked about P $\neq$ NP and with a similar answer -- the techniques/ideas used to prove the result would be the big breakthrough more so than the conclusion itself.
For Question 2 I want to share some background and a thought. Pretty much all the ...
15
Yes. We do know good lower bounds and we have known them for quite some time now.
Jerrum and Snir proved an exponential lower bound over monotone arithmetic circuits for the permanent by 1980. Valiant showed even a single minus gate is exponentially more powerful.
For more on (monotone) arithmetic circuits, check out Shpilka's survey on arithmetic circuits....
15
A nice question! Khrapchenko can definitely not give quadratic lower bounds for $AC^0$ functions. His lower bound is in fact at least square of average sensitivity. And all functions in $AC^0$ have poly-logarithmic average sensitivity. Subbotovskaya-Andreev can apparently also not give such a function because the argument they use (random restriction results ...
Only top voted, non community-wiki answers of a minimum length are eligible
