Questions tagged [boolean-complexity]

The tag has no usage guidance.

6 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1 vote
0 answers

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 ...
dino-t's user avatar
  • 13
1 vote
1 answer

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-...
lyberius's user avatar
1 vote
0 answers

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$, ...
Andrew Baker's user avatar
1 vote
0 answers

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 $...
user154975's user avatar
0 votes
0 answers

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&...
MattyZ's user avatar
  • 101
0 votes
0 answers

How to convert loop into combinational circuit?

In high-level programming languages, such as C and Python, loop statements such as while and ...
Emison Lu's user avatar