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....
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 by ...
18
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 ...
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
4,0152 gold badges23 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
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 ...
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
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.
17
Take $S_5$ as alphabet and
$$L= \{ \sigma_1\cdots \sigma_n \in S_5^*\mid \sigma_1\circ\cdots\circ\sigma_n = \text{Id}\}$$
Barrington proved in [2] that $L$ is $\textrm{NC}^1$-complete for $\textrm{AC}^0$ reduction (and even with a more restrictive reduction actually).
In particular this shows that regular languages are not in $\textrm{TC}^0$ if $\textrm{...
17
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 ...
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
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 ...
15
We know of no good lower bounds (meaning, say, a superpolynomial lower bound for a language in $\mathsf{NEXP}$) for depth 2 threshold circuits (unbounded weights). Depth 3 circuits built from majority gates, i.e. $\mathsf{TC}^0_3$ contains this class, and thus we know no good lower bounds for this class either.
answered Jun 11 '13 at 20:43
Kristoffer Arnsfelt Hansen
4,0152 gold badges23 silver badges34 bronze badges
15
1) What is meant by necessary is that one way to generate a $k$-wise independent distribution is to break the input in blocks of $k+1$ bits, and let the $(k+1)$th bit of each block be the parity of the other $k$ bits in the block. Obviously this distribution can be broken just by computing parity on $k$ bits. The result you claim follows from the fact that ...
15
There is a notion of a monotone non-deterministic and, more generally, alternating Turing machine in the paper Monotone Complexity by Grigni and Sipser. Since polynomial time is the same as alternating logarithmic space, a machine characterization of uniform $\mathsf{mP}$ is the monotone alternating logspace Turing machine. Providing such a machine with ...
15
Regular languages with unsolvable syntactic monoids are $\mathrm{NC}^1$-complete (due to Barrington; this is the underlying reason behind the more commonly quoted result that $\mathrm{NC}^1$ equals uniform width-5 branching programs). Thus, any such language is not in $\mathrm{TC}^0$ unless $\mathrm{TC}^0=\mathrm{NC}^1$.
My favorite $\mathrm{NC}^1$-...
15
A whole lot of fun things happen. Most of the ones I know of start with the IKW paper. There, the collapse $\textrm{NEXP} = \textrm{MA}$ is shown, and (I think) is the strongest literal collapse of complexity classes that we know of. There are other sorts of "collapses" though that I think should be pointed out.
Most importantly, I think, is the &...
15
Yes, any such pair can be separated by a formula of size $O(n)$. More generally, any disjoint pair $P,N\subseteq\{0,1\}^n$ of size $s=|P|+|N|$ can be separated by a decision tree of size $O(s)$, which can be implemented as an $O(s)$-size formula by replacing each query node with $(p\land\cdots)\lor(\neg p\land\cdots)$.
It suffices to observe that there ...
14
Following the suggestion of Kaveh, I am putting my comment as an (expanded) answer.
Concerning $Q1$, a word of caution is in order: even logarithmic depth if far from being understood, not speaking about poly-logarithmic. So, in the non-monotone world, the real problem is much less ambitious:
Beating Log-depth Problem: Prove a super-linear(!) lower bound ...
14
for Question 1, the answer is Yes, and can be shown as follows. (I will also be implicitly sketching an affirmative answer to Q4, since the argument is uniform and will treat all input lengths at once.)
Fix any NP-complete language $L$, and a family of good binary error-correcting codes (with rate 1/4 and correcting from a .1 fraction of errors, say). ...
14
To start off, there is of course Arora and Barak's book Computational Complexity: A Modern Approach. From there, parts 3 and 4 of Jukna's book Boolean Function Complexity: Advances and Frontiers make excellent reading material. Also, Ryan Williams teaches a nice course on circuit complexity whose course notes might hopefully be put up online :)
14
In addition to the ones suggested by Arnab, I would also recommend the following book:
Introduction to Circuit Complexity: A Uniform Approach by Heribert Vollmer
14
Let $f: \{0,1\}^* \rightarrow \{0,1\}$ be a function, and let $C$ be a class of algorithms working on finite slices of $f$. Every circuit lower bound whatsoever is a proof that $f \notin C$, for some $f$ and some $C$. Consider the "combinatorial property of Boolean functions" ${\cal P}_f$, such that
${\cal P}_f(f) = 1$ and ${\cal P}_f(g) = 0$ for all $g \...
13
According to Theorem 3.1 in Alexis Maciel and Denis Therien Threshold Circuits of Small Majority-Depth there is indeed a depth-3 circuit for computing the addition of two numbers.
The precise bound is $\Delta_2 \cdot \mathsf{NC}^0_1$ where $\Delta_2 = \Sigma_2 \cap \Pi_2$ are problems which have depth-2 $\mathsf{AC}^0$ circuits with both $\vee,\wedge$ ...
13
I believe the strongest is that $NEXP = MA$. This was proved by Impagliazzo Kabanets and Wigderson.
See https://scholar.google.com/scholar?cluster=17275091615053693892&hl=en&as_sdt=0,5&sciodt=0,5
I'd be also interested to know of any stronger collapses than this.
Edit (8/24): OK, I thought of some potentially stronger collapse, which ...
Only top voted, non community-wiki answers of a minimum length are eligible
