All Questions
Tagged with boolean-functions circuits
10 questions
4
votes
1
answer
148
views
Constructing vector valued boolean circuits from boolean circuits
This is a reference request. I'm
interested in the compositional construction of small boolean circuits
for vector-valued boolean functions $\phi : \mathbb{B}^m \rightarrow
\mathbb{B}^n$ for $n >...
- 11.6k
4
votes
0
answers
56
views
"Inverting" the fourier spectrum representation of a boolean function to recover a circuit representaiton
Given a boolean circuit, or an equivalent boolean expression, we can compute its fourier spectrum to yield a real-valued (multilinear) polynomial representation. What about the other way around? ...
3
votes
0
answers
108
views
Do random functions have synchronous, alternating circuits with non-injective first layers?
After discussing in the comments, I think a clearer definition of the question is as follows: for a random function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, what is the probability that there exists a ...
- 1,582
8
votes
1
answer
244
views
Monotone circuit representations of paths in a graph?
Consider a directed graph $G = (V, E)$ with a source $s \in V$ and sink $t \in V$. From $G$, I can define a monotone Boolean function $\phi_G$ on the set of variables $E$, in the following way: every ...
- 9,838
4
votes
0
answers
174
views
Improving boolean circuits w.r.t. a probability distribution
This is a reference request. Consider the following problem on boolean circuits [ 1 ]:
Given: Boolean circuit $B$ and probability distribution $\mathbb{P}$ on inputs to $B$.
Task: Find one or more ...
- 11.6k
-1
votes
1
answer
87
views
How to find for each 3-input boolean function the minimum number of NAND operators needed to compute it [closed]
I need to know for each of the $2^{2^3}$ boolean functions with $3$ inputs the
smallest boolean circuit made only of NAND gates computing it (smallest in terms
of the number gates).
I would be glad ...
- 1
7
votes
1
answer
223
views
Is Circuit Minimization $P$-hard under logspace reductions?
By Circuit Minimization, I am referring to the following decision problem.
Circuit Minimization
Input: A bit string $x$ and a number $k$.
Question: Does there exist a Boolean Circuit $C$...
- 5,167
2
votes
1
answer
98
views
Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994
This pertains to the proof of theorem 1.1 in this paper, http://dl.acm.org/citation.cfm?id=2897636
So Roychowdhury-Orlitsky-Siu had shown that the number of depth $2$ linear threshold gate circuits ...
- 1,453
11
votes
1
answer
381
views
Evaluate boolean circuit on batch of similar inputs
Suppose I have a boolean circuit $C$ that computes some function $f:\{0,1\}^n \to \{0,1\}$. Assume the circuit is composed of AND, OR, and NOT gates with fan-in and fan-out at most 2.
Let $x \in \{0,...
- 12.4k
5
votes
0
answers
122
views
Switching between representations of boolean functions between circuits and Fourier expansions
I'm currently learning about the analysis of boolean functions (mainly based on their Fourier coefficients) by reading this excellent resource
There, boolean functions are represented as linear ...
- 51