Questions tagged [boolean-functions]

Questions about Boolean functions and their analysis

72 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
449 views

283 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 ...
237 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 ...
488 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)+...
141 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 ...
119 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 ...
207 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 ...
301 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 ...
141 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'...
183 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 ...
197 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 ...
171 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 ...
116 views

219 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 132 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 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 121 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 174 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 173 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? ...