Questions tagged [boolean-complexity]
The boolean-complexity tag has no summary.
24 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
1
answer
71
views
3-CNF to 2-CNF reduction
I want to start by saying that I've struggled to find any satisfying answer to this question of mine. I did read this question, but it's slightly different.
My idea is simply that every 3-cnf formula ...
0
votes
0
answers
27
views
Identifying the DMAC Literals Representing Internal Processes (Message Schedule, T1, T2, etc.) in SHA-256 CNF Conversion Using CGen Tool
When using the CGen tool to convert the SHA-256 algorithm into Conjunctive Normal Form (CNF), the input and output bits are represented by DMAC literals. However, I am specifically interested in ...
0
votes
1
answer
64
views
Relationship between Formula Complexity and Depth Complexity of A Boolean Function
A (de Morgan) formula $\phi$ is a rooted binary tree, whose leaves are identified with
literals of the forms $x_i$ and $\neg x_i,ドル and whose internal vertices are labeled as AND ($\land$) or OR ($\lor$...
2
votes
1
answer
59
views
Convert the language into CNF or DNF form
A boolean circuit C has n inputs and m outputs, and is constructed with AND, OR, and NOT gates. Each gate has fan-in 2 except the NOT gate which has fan-in 1. The out-degree can be any number. A ...
0
votes
0
answers
65
views
Boolean circuit with true value
Let
$$L=\left\{,円\langle,円B_n,,円 ,円x,円\rangle:\enspace\substack{B_n \text{ is a boolean circuit and }
\\x \in \{0, 1\}^n\text{such that }B_n(x) = 1}\right\}$$
I want to prove that $L$ is $\textbf{P}$-...
3
votes
0
answers
35
views
Communication complexity of testing balancedness of a Boolean polynomial
The problem I consider is the following: given the 2ドル^n$ coefficients of a Boolean polynomial $f : \{0, 1\}^n \rightarrow \{0, 1\},ドル determine if $f$ is balanced namely if the truth table of $f$ ...
1
vote
2
answers
321
views
Boolean circuits with fan-out of each gate is 2
I am following the book of Arora and Barak book.
We consider Boolean circuits as we do, Specifically, inner nodes are either AND, OR (both – fan-in 2), or NOT (fan-in 1) gates. The fan-out of each ...
user avatar
user172436
2
votes
0
answers
79
views
Approximate the parity function in L1-norm
Consider the parity function $MOD_2(x) = x_1 \oplus \cdots \oplus x_n$ for $x \in \mathbb{F}_2^n$. I am concerned about the degree bounds for a real polynomial $f$ which approximates $MOD_2$ well in ...
2
votes
1
answer
117
views
Lower Bound on Parity of Boolean Functions
Let's say we have boolean functions $f_1, \cdots, f_n,ドル each of which operates on pairwise disjoint variables (i.e. the variables for each function are unique to that function). Then, how can we show ...
1
vote
1
answer
98
views
Algorithm design: Model redundancy in tests
I've run across an interesting problem at work that I'm not quite sure how to grapple.
Broadly, there is a suite of of $n$ tests to ensure the quality of a product. However, the tests are both time-...
1
vote
1
answer
297
views
How to construct a carry-lookahead adder of the optimal $O(n)$ size
Problem (TL;DR): I'd like to know how to construct a CLA adder that has $O(n)$ size and $O(\log n)$ depth using only fan-in 2 AND gates and XOR gates, as suggested in this answer and this answer.
...
0
votes
1
answer
220
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 ...
1
vote
0
answers
32
views
Why is End-Of-The-Line defined in terms of "Arithmetic circuits" instead of "Boolean circuits"
The definition of PPAD (Polynomial parity arguments on directed graphs) revolves around the definition of "End-Of-The-Line"
An exponentially large polynomial-depth arithmetic circuit, $f,ドル ...
1
vote
1
answer
116
views
Acyclic boolean circuit (DAG)
If a function f has a while loop or for loop, can I compile this function into an ...
0
votes
1
answer
47
views
influence of neighourhood points
Im trying to understand the following question. Suppose $h,f:\{-1,1\}^n\rightarrow \{-1,1\}$ satisfy $\sum_x h(x)f(x)\leq 0.5,ドル then one can rewrite this as $\textsf{Pr}_x [h(x)=f(x)]\leq 3/4$. Can we ...