All Questions
10 questions
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
4
votes
1
answer
272
views
Simple example of exponential gap between monotone and non-monotone circuits
Is there a simple example of a monotone Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone ...
D.W.♦
- 166k
3
votes
0
answers
111
views
Circuit complexity of hardest monotone function
Show there exists a monotone function $f\colon \{0,1\}^n \mapsto \{0,1\}$, such
that the minimal size of a monotone circuit that computes $f$ is
$\Omega(2^n / n^2)$. Use the fact that the number of ...
- 163
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
89
views
Relationship between circuit size and formula size in Sipser text
The Sipser text (3rd edition) contains a proof that 3-SAT is NP-Complete based on Boolean circuits. Part of the proof contains the remark that the reduction from the circuit to the Boolean formula can ...
- 947
1
vote
1
answer
48
views
Functions with small support have small circuits
I have been trying to understand the use of circuit models for boolean functions, and came across this question, that I am trying to struggle to understand:
Show that if a function $f\colon \{0,1\}^n→\...
- 13
1
vote
0
answers
21
views
Boolean circuit multigraph
Let us say that our definition of a circuit is the one of a boolean circuit from [Vollmer].
He uses directed acyclic graphs to represent circuits where the computation nodes are labeled with some ...
- 143
1
vote
0
answers
41
views
About sign-rank of Boolean functions
Do we know of any necessary condition for a Boolean function or say a depth $2$ LTF circuit to have a low (~poly(dim)) sign-rank?
- 493
0
votes
1
answer
122
views
LTF circuits and $AC^0$
Do we know if all of $AC^0$ can be captured by polynomial sized depth $2$ LTF circuits? (with or without polynomially bounded weights).
For any vector $w \in \mathbb{R}^n$ and any number $c \in \...
- 493
0
votes
1
answer
33
views
Taking mod $2$ with LTF gates
Consider the function : $\mathbb{Z}^{\geq 0} \rightarrow \{0,1\}$ given as $n \mapsto n \bmod 2$. Does this have an easy implementation using Linear Threshold Function gates?
I do not mean that the ...
- 493