Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [boolean-functions]

Questions about Boolean functions and their analysis

6
votes
1answer
108 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
114 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 : \{-1,1\}^n \xrightarrow{} \{-1,1\}$ $$ \max_{i \in [n]} \{\mathbf{Inf}_i[f] \} \geq \mathop{\bf Var}[f] \cdot \...
0
votes
0answers
52 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 ...
15
votes
0answers
224 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
98 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
158 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
116 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
111 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
177 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
59 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
40 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
181 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
551 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
162 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
135 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
101 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 ...
5
votes
2answers
364 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
149 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
110 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
150 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
159 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
141 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
182 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
143 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
118 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
82 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
197 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
75 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
46 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
77 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$ ...
1
vote
0answers
121 views

Boolean functions with high query complexity for PAC learning

The most general theorem for PAC learning of Boolean functions that I am aware of is the theorem in section 3.4 of Ryan O'Donnel's book where its basically shown that Boolean functions whose Fourier ...
13
votes
0answers
288 views

Fourier spectrum of the parity of two monotone Boolean functions

This is a question that I've been pondering, on and off, for a while, and unsuccessfully. I'd be very interested in any insight regarding this conjecture. (Or rather, these conjectures.) Recall that, ...
3
votes
0answers
130 views

Computing the Fourier expansion of the complete quadratic function

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$ $...
4
votes
0answers
121 views

About counting the “total size” of non-zero Fourier coefficients of a Boolean function

Given a $f: \{-1,1\}^n \rightarrow \mathbb{R}$, I want to compute this quantity, $\sum_{ \hat{f}(S) \neq 0, S \subseteq 2^{[n]}} \vert S \vert $ i.e the sum of the sizes of the subsets of $[n]$ ...
-1
votes
1answer
119 views

Sparsity of a Boolean function and its Fourier depth [closed]

For a function $f : \{-1,1\}^n \rightarrow \mathbb{R}$ one can ask for its $l_0$ norm in the indicator basis i.e the number of vertices on which the function is non-zero. Does this sparsity parameter ...
4
votes
0answers
100 views

Looking for an exposition of the proof of the LMN theorem

Is there any lecture note or review paper which gives a self-contained proof of the Linial-Mansour-Nisan theorem? The exposition of that in Ryan O'Donnel's book seems to use terminology and notation ...
7
votes
0answers
100 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 ...
7
votes
1answer
217 views

Is a monotone boolean function monotone as a multilinear polynomial?

Let $f:\{-1,1\}^n \rightarrow \{0,1\}$ be a monotonically increasing boolean function. That is, $f(x) \leq f(y)$, if coordinate-wise $x \leq y$. Now, let $F: [-1,1]^n \rightarrow \mathbb{R}$ be $f$ ...
7
votes
0answers
160 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 ...
3
votes
0answers
128 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 ...
7
votes
1answer
469 views

What is the VC Dimension of the $k-$Junta class

A boolean function $f(x_1,x_2,\dots,x_n)$ is $k$-Junta if it depends on at most $k$ variables. Consider the class $\mathcal{J}_{\leq k}$ of all $k$-Juntas over $n$ variables, what is the VC dimension ...
9
votes
1answer
275 views

Evaluate boolean circuit on batch of similar inputs

Suppose I have a boolean circuit $C$ that computes some function $f:\{0,1\}^n \to \{0,1\}$. Assume the circuit is composed of AND, OR, and NOT gates with fan-in and fan-out at most 2. Let $x \in \{0,...
5
votes
0answers
98 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 ...
-1
votes
1answer
87 views

Number of subexpressions in a boolean expression

I am wondering what the exact (including hidden constants) worst case number of subexpressions in an arbitrary boolean expression with $n$ literals (not necessarily distinct) is. For simplicity it is ...
7
votes
4answers
530 views

Do I have to give up the Law of the Excluded Middle in order to Learn $\lambda$-Calculus?

I know very little about what I am talking about in what follows, so I appreciate any all help in pointing out all of my mistakes -- otherwise I won't be able to learn more and advance in my knowledge ...
14
votes
0answers
533 views

Is it NP-hard to find (the root of) a small decision tree for a monotone boolean function?

Last year I spent some time trying to prove or disprove the following: Conjecture. Consider a graph $G$ and define a 2-DNF formula $\phi$ that contains a term $x \land y$ iff $x\mathrel{-\!-}y$ is ...
0
votes
0answers
59 views

Identity testing of margins of boolean functions

Consider a boolean function $f(\vec{x},\vec{y})$, we define an (integer-valued) function $g(\vec{x})=\sum_{\vec{y}}f(\vec{x},\vec{y})$, i.e., $g$ can be considered as a (sort of) margin of $f$. The ...
2
votes
0answers
72 views

Optimal boolean function encoding with bounded error

Let $F = \{f:\{0,1\}^n \to \{0,1\}\}$ be the set of all boolean functions on $n$ bits. Any such function can be written as a polynomial $f(x) = a_0 + \sum_i^n a_i x_i + \sum_{i,j}^n a_{i,j} x_i x_j + ...