Questions tagged [boolean-complexity]
The boolean-complexity tag has no usage guidance.
6
questions with no upvoted or accepted answers
1
vote
0
answers
38
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 ...
- 13
1
vote
1
answer
37
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-...
- 11
1
vote
0
answers
20
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$, ...
- 265
1
vote
0
answers
56
views
Formula for computing a specific Fourier coefficient of a boolean function
According to O'Donnell's book ``Analysis of Boolean Functions", in order to determine the Fourier coefficient of a boolean function $f$ on a subset $S$, we take an inner product of $\chi_S$ and $...
- 11
0
votes
0
answers
24
views
Solving the constraint portion of the input-encoding problem
The "input-encoding problem" is where the binary representations of symbolic input variables to a Boolean function are chosen to minimize the decode logic complexity. The "Espresso-MV&...
- 101
0
votes
0
answers
29
views
How to convert loop into combinational circuit?
In high-level programming languages, such as C and Python, loop statements such as while and ...
- 13