# Questions tagged [boolean-functions]

Questions about Boolean functions and their analysis

73 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
423 views

282 views

### Lower bound method for ordered binary decision diagrams

This is an idea/question inspired by the question and answer of Boolean functions with exponential size OBDD representation in all orders except one order?: If you want to prove some exponential ...
220 views

### Converting a Truth Table into k-CNF formula of Minimal Size in Linear Time

Let $T$ be a truth table of a boolean function $f$ on $n$ input bits. More concretely $T$ could be a list of length $2^n$ such that $T[i] = f(bin(i))$, where $bin(i)$ is the binary representation of ...
456 views

### Circuity complexity: monotone circuit of Majority function

As showed in the paper "Monotone Circuits for the Majority Function", is possible to construct a monotone boolean circuit for the majority function on n variables with size O(n^3) and depth 5.3 log(n)+...
136 views

### Are there generalizations for Chow's theorem?

The Chow's theorem as it stands holds only for a single linear threshold gate. That these gates are uniquely determined by their first $n+1$ Fourier coefficients. Are there other circuits for which ...
117 views

### Learning function with a few low-order Fourier coefficients, from uniformly random samples

Let $f:\{-1,+1\}^n \to \{-1,+1\}$ be a boolean function where all of the energy of the Fourier transform of $f$ is concentrated in a small number of low-order coefficients, say $k$ coefficients each ...
200 views

### An alternative proof of hypercontractivity of the Becker-Bonami operator

The Becker-Bonami operator $T_p$ on a function $f(x) : \{0,1\}^d \to \mathbb{R}$ is defined as follows. Let $\nu(x)$ be a perturbation of $x$ so that every bit remains the same with probability $p$ or ...
285 views

### Reverse Skolemization?

I'm wondering if there are any references on "reverse skolemization", that is, converting a formula with functions into one purely consisting of quantifiers by eliminating function applications. I'm ...
139 views

### Has what I am calling "helpfulness" here been studied?

We say that a Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ is helpful for another Boolean function $g$ if $f(x)$ can be computed with a smaller circuit given $g(x)$ as an extra input bit. I'...
174 views

### Is there a simple argument for this Hemi-Icosahedron Boolean function?

This is problem 1(e) from Homework 1 of the course about Analysis of Boolean functions at CMU in 2012 as well as problem 1.1(n) on p.34 of Ryan O'Donnell's Analysis of Boolean Functions. Compute the ...
193 views

### Bias of a random boolean low degree polynomial

What is the bias of a random Boolean function that can be represented as a low degree polynomial over the reals, i.e. has low Fourier degree? More specifically, is it true that if we take a uniformly ...
96 views

### Problems that reduce to or are abstracted by the learning juntas problem

What problems are either abstracted by or reduce to the learning juntas problem? (An example of a real-world problem abstracted by the learning juntas problem is the Identification of genetic loci ...
167 views

### Distributions over circuits and N-to-N vs N-to-1 circuits

This is really a two part question, and they aren't necessarily related. First, my understanding of natural proof barriers is that they are based on the idea that a suitable distribution over small ...
115 views

208 views

I am working through Ryan O' Donnell's book on the analysis of Boolean functions. One of the exercises (1.1) is to compute the Fourier series of the `complete quadratic function' on $\mathbf{F}_2^n$ $... 0answers 131 views ### Evaluating boolean formula without knowing all values I am looking for research approaches for the following problem: assume we have a set of$m$computers, each carries a bit, and a Boolean formula$\varphi$over those$m$variables. The computers are ... 0answers 332 views ### Why can't we have superlinear bounds on Boolean circuit size for an explicit function? I am interested about the minimal size (number of gates) of a family of circuits (with negation) over a complete Boolean basis (with fanin 2) that computes some explicit Boolean function. (In other ... 0answers 53 views ### moments of complexity for random restriction Suppose C is a large circuit computing a function$f:2^n \rightarrow 2^m$. For a function$g$let$B(g)$denote the size of the minimal Boolean circuit computing$g$. What can be said about the ... 0answers 110 views ### What is the current state of research on the representation of boolean functions using wavelets The harmonic representation of boolean functions such as XOR or AND has been studied in different course note lectures that can be found on Google. http://cs.mcgill.ca/~hatami/comp760-2011/ http://... 0answers 115 views ### Social choice theory, preference aggregation data sets I do computational research on preference aggregation. I am quite interested in Kemeny Optimal Aggregation. However I do not find much useful data for preference aggregation in context of social ... 0answers 171 views ### Deciding whether a binary multiplicity automaton has empty language Multiplicity automatons (see here) is an interesting model. They have the (almost) same syntax as a non-deterministic finite automatons, but instead of deciding whether a word belongs to a language, ... 0answers 170 views ### An identity about the Majority function? Let$f:\{-1,1\}^n \rightarrow \{-1,1\}$be any boolean function. Let$Maj_n$represent the majority function. Let$\langle f,g \rangle = E[f(x)g(x)]$and$\mathcal{I}(f) = E_x[\# i, s.t. f(x)\neq f(x \...
Given a balanced Boolean function $f:\{0,1\}^n\mapsto\{0,1\}$, is there a sampling strategy that needs less than $O(2^n)$ samples to estimate the average length of contiguous sequences of 1's? ...