# 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
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 ...
1 vote
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-...
1 vote
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$, ...
1 vote
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 \$...