All Questions
11 questions
0
votes
1
answer
191
views
Given a boolean circuit that computes a boolean function, can we always find an equivalent circuit with optimal size?
Let's say that we have a decision problem $P$. Let's also say that $I_n$ is the set of all instances of size $n$ that exist for this problem, and that its cardinality is finite.
There is a sequence of ...
- 145
2
votes
0
answers
93
views
Prove lower bound on boolean circuit
Given matrix $A \in \{0,1\}^{n \times m}$ with $n$ rows and $m = 2^n - 1$ columns. Where $j$-th column is binary decomposition of $j$ ($j = 1 \dots 2^n - 1$). For example, if $n = 3$:
$ A = \begin{...
- 105
1
vote
1
answer
152
views
Connection between Pseudo random generators and hardness
For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$ $H_{avg}(f)$ is defined as the largest $S(n)$ s.t. for all circuit $C_n$ of size $S(n)$, $\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $...
- 246
3
votes
1
answer
101
views
Counting circuits with constraints
Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one).
In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be ...
- 33
5
votes
3
answers
947
views
Is Green's the best 16-input sorting network so far?
Every paper says that Green's construction is the best 16-input sorting
network as for now.
But why does Wikipedia says: "Size, lower bound: 53"?
I thought "lower bound" meant:"If there exists at ...
- 153
5
votes
1
answer
192
views
Lower bound of degree of polynomial approximating parity
Let $\text{MOD}_2 : \{0,1\}^n \rightarrow \{0,1\}$ be a parity function where $$\text{MOD}_2(x_1,\dots,x_n) = \sum_i x_i \bmod 2$$
It is known [See e.g. Lemma 5 of this lecture note] that any ...
- 283
6
votes
1
answer
330
views
Is there an intuitive proof for the existence of hard functions?
I am referring to the theorem on page 115 of the book by Arora and Barak, which states that, ``For every $n>1$, there exists a function $f:\{0,1\}^n \rightarrow \{0,1\}$ that cannot be computed by ...
- 1,165
7
votes
1
answer
413
views
Implications of the $\Omega(\frac{2^n}{n})$ circuit lower bound being tight
There is a basic result in circuit complexity that says:
There exists a language that cannot be solved with circuits of size $o(\frac{2^n}{n})$.
The argument is a simple counting argument on the ...
- 579
2
votes
0
answers
40
views
From SETH to circuit lowerbounds
Are there reductions from SETH (Strong Exponential Time Hypothesis) to lowerbounds against threshold circuits? (maybe for computing Boolean functions of the form OR-of-AND-of-OR)
In threshold ...
- 493
0
votes
0
answers
46
views
Circuit Lower bound for $EXP^{NP}$
By Burhman, Fortnow and Thierauf result Paper Link, we know that $MA_{EXP} \not\subset P/poly$.
Also, we know that $MA \subseteq P^{NP}$ (or $\Delta_{2}^{P}$ in some literatures).
By using the ...
- 393
5
votes
1
answer
269
views
Simple lower bounds against AC0
It is known that $Parity \notin AC^0$ (nonuniform), but the proof is rather involved and combinatorial. Are there simpler, but weaker lower bounds, say for $NP \not \subseteq AC^0$ or $NEXP \not \...
- 3,501