Questions tagged [boolean-complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers
50 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 ...
TheGuy's user avatar
  • 21
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&...
MattyZ's user avatar
  • 101
2 votes
1 answer
74 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 ...
dino-t's user avatar
  • 23
1 vote
1 answer
43 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-...
lyberius's user avatar
1 vote
1 answer
101 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. ...
AXX's user avatar
  • 31
0 votes
1 answer
151 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 ...
Alonso Montero's user avatar
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$, ...
Andrew Baker's user avatar
1 vote
1 answer
64 views

Acyclic boolean circuit (DAG)

If a function f has a while loop or for loop, can I compile this function into an ...
Emison Lu's user avatar
0 votes
1 answer
22 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 ...
wwjohnsmith's user avatar
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 $...
user154975's user avatar
0 votes
1 answer
83 views

Is there a notation for boolean algebra complexity?

To represent complexity of an algorithm, Computer Scientist is used to using big-O notation. How about complexity of boolean algebra? Boolean algebra is commonly used in digital circuit design with ...
Muhammad Ikhwan Perwira's user avatar
0 votes
1 answer
395 views

Time-complexity of evaluating a CNF formula

Given a Boolean formula over $n$ variables in CNF and a partial assignment to it, all the algorithms I can think of to evaluate the assignment run in time $\Theta(n^2)$. Is it possible to do it in $O(...
Noel Arteche's user avatar
1 vote
1 answer
76 views

How many different boolean functions exist up to permutation of its $n$ variables

i am relatively new here, so if this was asked before, feel free to redirect me. I am searching for an answer in form of a (iterative or recursive) Formula or even better, an algorithm to list them ...
vreithinger's user avatar
1 vote
1 answer
57 views

Can Boolean circuits of polylog depth represent all Boolean functions?

Consider a Boolean circuit using (2-input) logical-and, (2-input) logical-or and logical-not as basic components. The depth of the Boolean circuit is the length of the longest path from the input to ...
zbh2047's user avatar
  • 296
3 votes
1 answer
718 views

Shannon's result that some Boolean functions require exponential circuits

In 1949 Shannon proved, using a non-constructive counting argument, that some boolean functions have exponential circuit complexity, see [1] and many texts on computational complexity. This result has ...
Martin Berger's user avatar
2 votes
1 answer
67 views

Is $f(X)f^d(X) = 0$ for a Boolean function $f$?

I'm currently trying to understand a step in the proof for in the Crama and Hammer book on Boolean Functions. The proof is Proposition 4.12, which claims that the self-dualization of Boolean $f$ is ...
Berk U.'s user avatar
  • 429
2 votes
1 answer
29 views

sum of Boolean characters larger degree

I was curious if someone knew the answer/reference for the following. So it is well-known that if $S\in \{0,1\}^n$, then $$ \frac{1}{2^n}\sum_{x\in \{0,1\}^n} (-1)^{\langle S, x\rangle}=1 $$ if and ...
postasguest's user avatar
1 vote
1 answer
33 views

Boolean function represented as a column vector: easy way to see if it has full degree?

If you have a Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$ on $n$ variables, you can represent this function as a $2^n$ vector indexed by the input space such that $ f_x = f(x)$. For ...
gen's user avatar
  • 991