Questions tagged [boolean-functions]
Questions about Boolean functions and their analysis
183
questions
-1
votes
1answer
47 views
How to find for each 3-input boolean function the minimum number of NAND operators needed to compute it [closed]
I need to know for each of the $2^{2^3}$ boolean functions with $3$ inputs the
smallest boolean circuit made only of NAND gates computing it (smallest in terms
of the number gates).
I would be glad ...
-1
votes
0answers
40 views
What is the most efficient algorithm for computing the probability that an arbitrary Boolean function outputs 1 for a random input?
Given a Boolean function that can be expressed using universal logic gates (e.g. NAND), has $n$ inputs, and has a single output, what is the most efficient algorithm that can compute the probability ...
3
votes
1answer
168 views
Level $k$ bounds in Analysis of Boolean functions
In Ryan O'Donnell's book Analysis of Boolean functions, following Corollary 9.25 the following appears:
If $f\colon \{-1,1\}^n \to \{0,1\}$, and we have $\mathbb{E}[f] = \alpha$, then for any integer ...
5
votes
1answer
100 views
Majority function stability under deletion and addition of entries
It is well known that the majority function is stable under random flipping of bits. That is, if $v$ is a random binary vector, and then we re-sample each bit of $v$ with probability $\delta$ and get $...
4
votes
1answer
275 views
Maximization of Mutual Information
Let $X\in\{0,1\}^d$ be a Boolean vector and $Y, Z\in\{0,1\}$ are Boolean variables. Assume that there is a joint distribution $\mathcal{D}$ over $Y, Z$ and we'd like to find a joint distribution $\...
3
votes
1answer
137 views
Dual to hypercontractive inequality
Recall the hypercontractive inequality:
Let $\rho = \sqrt{\frac{p-1}{q-1}}$, then $||T_\rho(f)||_q \leq ||f||_p$
In https://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf it is stated that the ...
7
votes
0answers
165 views
Lighting up all elements of a poset by toggling upsets
I consider the following game on a finite poset $(P, <)$. At each point of the game, I have a set of elements $S$ of the poset which are "on", and all others are "off". Initially $S = \emptyset$. ...
4
votes
1answer
214 views
How tight is the XOR lemma?
The XOR lemma states that if you have a distribution $D$ on $\{0,1\}^n$, and all the Fourier coefficients of $2^n D$ are small, then it is close in $L_1$ to the uniform distribution. Specifically, ...
1
vote
0answers
77 views
Cover set of Boolean formulas with conjunctions
I want to cover a set of Boolean formulas (over the same variables) with disjunctive conjunctions. Here's an example with two formulas $p_1$ and $p_2$ over the set of variables $\{A, B, X, Y\}$:
I ...
4
votes
0answers
118 views
Characterizing the ANF of Single-Cycle Boolean Permutations
Given a function $F: \{0, 1\}^n \to \{0, 1\}^n$, we say that $F$ is a boolean permutation (also sometimes called a vectorial boolean function or an s-box in the literature) if $F$ is a bijection. We ...
8
votes
1answer
1k views
On the sensitivity conjecture?
The recent establishment of the relation $bs(f)=O(s(f)^4)$ goes through Gotsman,Linial .
Can the same approach get to $O(s(f)^2)$ or is there an essential limitation to the approach?
2
votes
0answers
116 views
Sensitivity and Low-Degree Approximation under Non-Uniform Distribution
I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
13
votes
0answers
206 views
Which monotone DNFs are evasive?
A Boolean function $\phi$ on variables $X$ is evasive if every decision tree for $\phi$ has height $|X|$. In other words, for any strategy that picks variables of $X$ and asks for their value, an ...
3
votes
1answer
134 views
Given a subset of of the hypercube and an affine transform of it, find the affine map
This is a follow up to this resolved question.
Suppose we are given a set of bitvectors $A\subseteq\mathbb{F}_2^d$ and an invertible affine transformed copy of it
$$B=\{Mx + s\mid x\in A\}$$
for some ...
7
votes
2answers
319 views
Given a subset of the hypercube and a copy translated by s, find s
Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible ...
7
votes
0answers
235 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 ...
23
votes
2answers
593 views
Question about two matrices: Hadamard v. “the magical one” in the proof of the sensitivity conjecture
The recent and incredibly slick proof of the sensitivity conjecture relies on the explicit* construction of a matrix $A_n\in\{-1,0,1\}^{2^n\times 2^n}$, defined recursively as follows:
$$A_1 = \begin{...
1
vote
0answers
50 views
relations between the degrees of a boolean function and its absolute function
Given a boolean function $f:\{0,1\}^n\rightarrow\mathbb{R}$ of degree $d$, is there any upper bound in terms of $d$ on the degree of the function $|f|$, where $|f|(x)=|f(x)|$. Here the degree of $f$ ...
7
votes
1answer
152 views
Sampling monotone Boolean functions
I'm interested in sampling monotone increasing Boolean functions on $n$ input bits uniformly at random. I understand that this is equivalent to approximating the Dedekind numbers ($D_n = $ the number ...
4
votes
1answer
176 views
Which (almost) balanced Boolean function has smallest “total” influence
The well known Kahn–Kalai–Linial (KKL) Theorem says that for any Boolean function $f\colon \{-1,1\}^n \xrightarrow{} \{-1,1\}$
$$
\max_{i \in [n]} \{\mathbf{Inf}_i[f] \} \geq \mathop{\bf Var}[f] \cdot ...
0
votes
0answers
56 views
Which research fields deal with this variant definition of Boolean circuit depth?
Disclaimer: I admit that the question is not very clear. I think it cannot be helped because the question is very open-ended.
First of all, I present the interested type of circuits. We only consider ...
17
votes
0answers
351 views
Perfect matching of monotone Boolean function with null Euler characteristic
For a set $V = \{0,\ldots,k\}$ of variables, let $\mathbf{G}_V$ be the undirected graph with set of vertices $\{S \subseteq V\}$ and set of edges $\{\{S,S'\} \mid S \subseteq S' \text{ and }|S'| = |S|+...
3
votes
0answers
107 views
Is Circuit Minimization $P$-hard under logspace reductions?
By Circuit Minimization, I am referring to the following decision problem.
Circuit Minimization
Input: A bit string $x$ and a number $k$.
Question: Does there exist a Boolean Circuit $C$...
5
votes
1answer
168 views
Minimal information needed for determine some function
From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of ...
6
votes
1answer
121 views
Average-case analogue of Small-bias Spaces
Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that for every non-zero linear test $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias
$$| \mathbb{E}_{x \in S} [ (-...
3
votes
0answers
112 views
Decomposition of rectangular relations
Let $\alpha$ be a binary relation from $\gamma$ to $\chi$ and $\beta$ a binary relation from $\chi$ to $\rho$. If both $\alpha$ and $\beta$ are rectangular, i.e., they satisfy $\alpha \alpha^{-1} \...
9
votes
1answer
184 views
Has there been any progress in tightening the exponent in the result that polylog independence fools $AC_0$?
Braverman showed that distributions which are $(log \frac{m}{\epsilon})^{O(d^2)}$-wise independent $\epsilon$-fool depth $d$ $AC^0$ circuits of size $m$ by "gluing together" the Smolensky ...
1
vote
0answers
66 views
Relative Two-Function Hypercontractive Inequality $\langle T_{\rho\sigma} f,g \rangle \le \langle T_{\sigma} f,g \rangle^q$
The hypercontractive theorem (or Bonami Beckner inequality) says (Ryan O'Donnell):
This of course also directly gives the 'intermediate' inequality $\|T_{\rho\sigma}f\|_q \le \|T_\sigma f\|_{1+(q-1)\...
2
votes
0answers
48 views
$p$-biased two-function hypercontractivity
The Hypercontractivity theorem (or Bonami Beckner inequality) is a very useful tool. Unfortunately, it isn't easy to carry over to other spaces than the uniform boolean cube.
In Ryan O'Donnel's ...
2
votes
1answer
191 views
Fourier decomposition in terms of another basis
Given a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$, it is well know that the Fourier decomposition of $f$ can be written as $f(x)=\sum_{S\subseteq \{1,\ldots,n\}} \widehat{f}(S) \prod_{i\in S}...
6
votes
2answers
600 views
a polynomial representation of boolean functions
I came up with this linear transformation to map boolean functions to polynomials and it seems to have some nice properties. I was wondering if there is any reference describing this (and/or similar) ...
3
votes
1answer
171 views
Proof that all Boolean functions can be computed by $(MOD_2-MOD_3)$ circuit
I was reading "Some properties of MOD m circuits computing simple functions" (Amano & Maruoka, 2003) where the authors prove that every Boolean function can be computed by depth $2$ by $(MOD_2-...
6
votes
0answers
138 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'...
1
vote
1answer
106 views
How good of an approximate 2-coloring can you get of the halved cube graph?
We say that a 2-coloring $col : V_G \rightarrow \{0, 1\}$ of a graph $G$ is $\epsilon$-approximate if $Pr_{(w, v) \in E_G}(col(w) \neq col(v)) \geq \epsilon$. For every $n$, what is the maximum $\...
1
vote
0answers
76 views
Reference request for the relationship between approximating degree of Boolean functions and learning algorithms
This paper (http://www.cs.columbia.edu/~rocco/Public/stoc01.pdf) from STOC 2001 is possibly the first paper to show how to convert upperbounds on the $\frac{1}{3}-$approximation degree of a Boolean ...
10
votes
3answers
497 views
Proper PAC learning VC dimension bounds
It is well known that for a concept class $\mathcal{C}$ with VC dimension $d$, it suffices to obtain $O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$ labelled examples to PAC learn $\...
9
votes
1answer
160 views
What is the probability that a random Boolean function has a trivial automorphism group?
Given a Boolean function $f$, we have the automorphism group $Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \}$.
Are there any known bounds on $Pr_f(Aut(f) \neq 1)$? Is there ...
4
votes
0answers
116 views
Relationship between sparsity and rank of a boolean function
I have the following question when I was going through the proof of the following theorem.
Theorem. For XOR function $f \circ XOR$, $rank(M_{f \circ XOR}) = ||\hat f ||_0$ where $M_{f \circ XOR}$ is ...
2
votes
1answer
49 views
Certainty of mutual confirmation over faulty channels?
This is a very theoretical question, although I am sure the problem pops up in lots of IT and automation applications. Still, I prefer to formulate it in an action-movie scenario (a bit of the ...
1
vote
1answer
158 views
Proof of Majority is stablest in “reverse” in the MAXCUT hardness paper by Khot et al
This is about Proposition 7.4 here. I think there is a slight error in the proof of this proposition. Basically, authors have taken $g$ to be the odd part of the function $f$. Due to which we can say ...
4
votes
1answer
170 views
Möbius values of CNF and DNF lattices of a monotone Boolean function
Let $\phi$ be a monotone Boolean function on a set of variables $\langle k \rangle := \{0,\ldots,k\}$ such that $\phi$ depends on all the variables in $\langle k \rangle$ (that is, for every variable $...
3
votes
1answer
153 views
Basic property of boolean functions with restrictions
For $f:\{\pm1\}^n\to\mathbb{R}$, $I\subset\{1,\dots,n\}$ and $x\in\{\pm1\}^{\{1,\dots,n\}\setminus I}$ we define $f_I[x]:\{\pm1\}^I\to\mathbb{R}$ by $f_I[x](y)=f(x,y)$. (We denote by ($x,y$) the ...
2
votes
0answers
187 views
Proof of a (simple) lemma by Aaronson
I am reading this article, and I need help with an apparently obvious proof.
The lemma (on page 5), that I want to know the proof of, is this: Let $p : \{0,1\}^N \rightarrow \mathbb{R}$ be a real ...
2
votes
0answers
158 views
Oracle for Hamming distance to a secret bitvector
Let $s \in \{0,1\}^n$ be a secret bitvector. Define $f(x)$ to be the Hamming distance between $x$ and $s$. Suppose I am given an oracle for $f$, and I want to find $x$. How many queries to the ...
6
votes
0answers
123 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 ...
1
vote
1answer
86 views
Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994
This pertains to the proof of theorem 1.1 in this paper, http://dl.acm.org/citation.cfm?id=2897636
So Roychowdhury-Orlitsky-Siu had shown that the number of depth $2$ linear threshold gate circuits ...
8
votes
1answer
198 views
variant of Critical SAT
The language Critical SAT is defined as the set of $CNF$ boolean formulas $f$ such that $f \in UNSAT$ but removing any clause from $f$ makes it satisfiable. It is known that Critical SAT is $DP$-...
4
votes
0answers
78 views
About Boolean functions with a high sign-rank
Recently in this beautiful paper, https://arxiv.org/pdf/1705.02397.pdf it has been shown that there is an explicit $Th \circ Th$ function with sign-rank scaling exponentially in dimension. I wanted to ...
2
votes
0answers
49 views
Complexity class of MCS and relation to #p
I was looking for the complexity class of computing MCS:
Given a boolean formula $\mathcal{F = c_1 \wedge c_2,...,\wedge c_m}$ represented in CNF, a MCS is a subset of the set of clauses $\mathcal{C}$ ...
1
vote
0answers
82 views
Tribes function vs (modified) polynomial threshold circuits
Are there lowerbounds known for representing the Tribes function by a circuit consisting of a single layer of polynomial threshold gates feeding into maybe a trivial summing gate? (Even for degree $1$ ...
