All Questions
4 questions with no upvoted or accepted answers
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
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