Skip to main content

Questions tagged [boolean-functions]

Questions about Boolean functions and their analysis

Filter by
Sorted by
Tagged with
4 votes
1 answer
130 views

Constructing vector valued boolean circuits from boolean circuits

This is a reference request. I'm interested in the compositional construction of small boolean circuits for vector-valued boolean functions $\phi : \mathbb{B}^m \rightarrow \mathbb{B}^n$ for $n >...
Martin Berger's user avatar
5 votes
0 answers
73 views

Hardness of Computing Tribes-DNF by Decision Trees

In this paper on "The Polynomial Hierarchy, Random Oracles, and Boolean Circuits", Fact (3.2) states that it is impossible for a polylogarithmic depth decision tree to compute the Tribes-DNF ...
CHLander's user avatar
2 votes
0 answers
68 views

Distance between Fourier distributions of independent random Boolean functions

For a boolean function $f: \{-1,+1\}^n \to \{-1,+1\}$, the squared Fourier coefficients $\{\hat{f}(S)^2\}_{S \subseteq \{0,1\}^n}$ form a probability distribution. I want to know what the total ...
helloworld's user avatar
4 votes
0 answers
53 views

"Inverting" the fourier spectrum representation of a boolean function to recover a circuit representaiton

Given a boolean circuit, or an equivalent boolean expression, we can compute its fourier spectrum to yield a real-valued (multilinear) polynomial representation. What about the other way around? ...
Thomas Shrimpton's user avatar
3 votes
0 answers
51 views

Name for the dimension of subspace of support of boolean function?

The support of a boolean function is defined as the set of $x$ such that $f(x) = 1$. I want to quantify the dimension of the support of the function (i.e. how large the subspace is that is made up of ...
wecanfibonacciit's user avatar
8 votes
3 answers
332 views

Relationship between size of Boolean functions and DFAs

Are there any works that study the relationship between Boolean functions and the size of the minimal DFAs required to represent those Boolean functions? Boolean functions refer to the usual ...
Satwik's user avatar
  • 181
1 vote
0 answers
55 views

Number of ${\tt NAND}$-gates needed to build any $n$-ary Boolean function

Are there positive integers $k,c$ with the following property? Whenever $n$ is a positive integer, then any function $$f:\{0,1\}^n\to\{0,1\}$$ can be built using at most $n^k+c$ ${\tt NAND}$-gates ...
Dominic van der Zypen's user avatar
0 votes
0 answers
47 views

Is it possible to estimate the positive outcomes of a boolean function using an optimized version of Goldreich-Levin?

Let $\mathcal{X} = \{-1,1\}^n$ and $h: \mathcal{X} \to \{-1,1\}$, h can be expanded in the basis of monomials for the uniform distribution, or also can have a distribution free expansion (Gram-Schmidt ...
rivana's user avatar
  • 65
3 votes
1 answer
399 views

Intuition on Lupanov's Upper Bound on Circuit Size

The following result, by Lupanov, is a classic in the theory of Boolean function complexity: Theorem: For every boolean function $f$ of $n$ variables: $$C(f) \leq (1 + \alpha_n)\frac{2^n}{n}, \text{ ...
sdsdsd's user avatar
  • 133
2 votes
0 answers
48 views

Does Goldreich-Levin algorithm for finding large Fourier coefficients have time complexity upper bound = sample complexity upper bound?

I'm currently working on finding better bounds for Goldreich-Levin algorithm for estimating large Fourier coefficients of a boolean function. I was surprised seeing that the upper bounds for time ...
rivana's user avatar
  • 65
1 vote
0 answers
54 views

Is there an efficient Goldreich-Levin algorithm that generalizes to agnostic PAC setting?

Goldreich Levin algorithm is an algorithm that based on some assumption (boundness on Fourier coefficients) outputs the indices for most significant Fourier coefficients of a boolean function, however ...
rivana's user avatar
  • 65
1 vote
0 answers
77 views

Testing positivity of a function by an IP system?

We are given a polynomial function $f:\{0,1\}^n\to\mathbb{R}$ with $\text{deg}(f)\leq d$ ($d$ is constant), and $\epsilon>0$; $f$ here is presented by its coefficients (the degree is constant, so ...
qmww987's user avatar
  • 111
3 votes
0 answers
99 views

Influence for boolean functions on larger domains

Most of the literature on boolean function complexity considers boolean functions on $\{0,1\}^n$, but I am not finding very much about functions over larger (finite) domains. Specifically, fix a ...
user6584's user avatar
  • 1,242
4 votes
1 answer
185 views

Concrete version of KKL Theorem

The Kahn–Kalai–Linial (KKL) Theorem says that for any balanced Boolean function $f:\{−1,1\}^n→\{−1,1\}$ we have $\max_i {\bf Inf}_i(f) = \Omega\left(\frac{\log n}{n}\right)$. I am looking for a ...
user6584's user avatar
  • 1,242
1 vote
0 answers
52 views

Maximum degree of the Sum of Squares certificate of a non-negative degree d polynomial on the boolean hypercube

Let $f: \{0, 1\}^n \rightarrow \mathbb R$ be a polynomial on the boolean hypercube. If $f$ is non-negative $(f \geq 0)$ i.e. $f(x) \geq 0, \forall x \in \{0, 1\}^n$ then $f$ always has a degree $2n$ ...
Subhadeep's user avatar
  • 111
-1 votes
2 answers
171 views

Finding an $\epsilon$-concentrated collection with size in terms of spectral $1$-norm

$\newcommand{\R}{\mathbb{R}}$ This question is about Problem 3.16 in Ryan O'Donnell's Analysis of Boolean Functions book. The problem is stated as follows: Let $f : \{-1,1\}^n\to\R$ and let $\epsilon&...
Ash's user avatar
  • 49
1 vote
1 answer
171 views

If boolean function $f$ is computable by a k-CNF and an l-DNF then it can be computed by a decision tree of depth at most kl

I have seen it stated that if boolean function $f$ is computable by a $k$-CNF and an $l$-DNF then it can be computed by a decision tree of depth at most $kl$. However, I am not able to see why this is ...
TheCollegeStudent's user avatar
0 votes
1 answer
156 views

What is the simplest one-way function (in terms of boolean circuit complexity)?

What is the simplest known one-way function? By simplest, I mean, when implemented as boolean logic, the number of AND/OR/NOT gates needed is minimal (smallest circuit complexity). (I'm trying to find ...
Azuresonance's user avatar
2 votes
1 answer
206 views

Value of studying boolean function complexity through circuits complexity nowadays

Apparently boolean function complexity analysis through circuit complexity has a limit (as they are natural proofs), and this means it is not possible to proof $P \not= NP$ unless there are no one-way ...
Wilmer Bandres Hernández's user avatar
2 votes
1 answer
141 views

Counting argument for LTF circuits

In Boolean circuit complexity, Shanon's counting argument shows that a random Boolean function on $n$-input bits requires a circuit of size $\Omega(2^n/n)$ to be computed by a circuit made of AND, OR ...
Tulasi's user avatar
  • 327
8 votes
1 answer
154 views

Reductions and projections in circuit complexity

I'm struggling to find a good reference that defines the difference between projection and monotone projection in the context of Boolean functions and circuit complexity. My understanding is that a ...
Noel Arteche's user avatar
7 votes
1 answer
188 views

Complexity of Maximizing Hamming Distances Below a Threshold

Problem Statement Is the following problem NP-Complete? Input: A collection $S$ of binary strings, with each string of length $m$. Goal: Compute a binary string $s^*$ of length $m$ that mazimizes the ...
B A's user avatar
  • 98
2 votes
0 answers
62 views

Learning boolean functions with input-ouput examples and side-information

The Kushilevitz-Mansour, "low-degree", and Goldreich-Levin algorithms aim to learn a function $f: \{0,1\}^n \rightarrow \{0,1\}$ from a sufficiently large set of input-output examples $(x_i, ...
Tom Shrimpton's user avatar
0 votes
0 answers
94 views

Boolean vs algebraic circuits difference

Valiant, Skyum, Berkowitz and Rackoff in https://epubs.siam.org/doi/10.1137/0212043 showed that $VP=VNC^2$, namely, that arithmetic circuits can be parallelized. What is the central reason such a ...
Turbo's user avatar
  • 13k
0 votes
0 answers
60 views

Is there a name/terminology for binary codes with evenly spaced number of ones?

I am generating a random binary matrix $A \in \{0, 1\}^{m \times n}$ with the number of ones in each row set to evenly spaced numbers from an interval. For example, if $n=50$, the number of ones for $...
randomprime's user avatar
2 votes
0 answers
97 views

Natural proofs and size of propositional formulas

Given a formula $\phi$ of propositional logic, we define its size $|\phi|$ as the number of proposition symbols that $\phi$ contains (counted with multiplicity). For example, $|(p \land p)| = 2$. Let $...
Reijo Jaakkola's user avatar
5 votes
0 answers
126 views

Complexity of approximating boolean functions with circuits

Let $f$ be a boolean function on $n$ variables - say we want to find the smallest circuit $C$ where $C(x)=f(x)$ for all but an $\epsilon$ fraction of inputs $x \in \{0,1\}^n$. What is known about the ...
Igor Ferst's user avatar
3 votes
1 answer
196 views

XORSAT to HornSAT reduction

I am trying to write a practical piece of code that solves a XORSAT by first reducing it to HornSAT and then solving the HornSAT (instead of doing Gaussian Elimination over F2). The reason for this ...
Fabio Dias's user avatar
3 votes
0 answers
106 views

Do random functions have synchronous, alternating circuits with non-injective first layers?

After discussing in the comments, I think a clearer definition of the question is as follows: for a random function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, what is the probability that there exists a ...
Samuel Schlesinger's user avatar
2 votes
2 answers
350 views

What is the polynomial representation of the Hamming weight function?

For any function $f: \{1,-1\}^n \rightarrow \{1,-1\}$, there is a unique multilinear polynomial $p \in \mathbb{R}[x_1,\dots, x_n]$ for which $p(x)=f(x)$ for all $x \in \{1,-1\}^n$ (see e.g. Lemma 4.1 ...
Ben's user avatar
  • 123
1 vote
1 answer
296 views

KRW Conjecture: separation of NC^1 and P

More than a real question this is a recap of something I have been studying. I hope someone will help me getting things straight, so any correction or thought about the following reasoning is more ...
Pietro D'Amico's user avatar
8 votes
1 answer
235 views

Monotone circuit representations of paths in a graph?

Consider a directed graph $G = (V, E)$ with a source $s \in V$ and sink $t \in V$. From $G$, I can define a monotone Boolean function $\phi_G$ on the set of variables $E$, in the following way: every ...
a3nm's user avatar
  • 9,527
3 votes
1 answer
161 views

$ACC^0$ implementation of a boolean function

Consider the symmetric boolean function $$F(x_1,\dots,x_n)=1\iff\sum_{i=1}^nx_i\mbox{ is a square}.$$ It is implementable in $TC^0$. Is there an $ACC^0$ implementation? The reason I ask is there seems ...
User2021's user avatar
4 votes
0 answers
87 views

Harmonic analysis of sequences of Boolean functions (i.e. of words in $(\{0,1\}^n)^*$)

Is there any research on harmonic analysis of sequences of Boolean functions, which represent the application of a Boolean function on a word in $(\{0,1\}^n)^*$? I'm looking for any reference on this, ...
Shaull's user avatar
  • 5,656
5 votes
1 answer
453 views

A boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$ is chosen at random from all $2^{2^n}$ such $f$. What do the Fourier coefficients look like?

As in the title. I'm not sure where to start here. My guess is that in expectation at least a constant fraction are non zero, and as a result there would exist some "large" coefs. and some "small" ...
zfkmz's user avatar
  • 187
3 votes
0 answers
111 views

Improving boolean circuits w.r.t. a probability distribution

This is a reference request. Consider the following problem on boolean circuits [ 1 ]: Given: Boolean circuit $B$ and probability distribution $\mathbb{P}$ on inputs to $B$. Task: Find one or more ...
Martin Berger's user avatar
6 votes
1 answer
439 views

Is the basis of parity functions the only orthonormal basis for Boolean functions?

Is there another orthonormal basis of functions for Boolean functions? Or, more specifically, besides the parity functions, is there another explicit function (which is common and has a name) that can ...
tigercub97's user avatar
7 votes
1 answer
387 views

Complexity of constructing minimum depth decision trees

I am interested in the computational complexity of Problem 1: Given a finite, non-empty set $J$, given $A, B \subseteq \{0,1\}^J$ such that $A \cap B = \emptyset$, and given $n \in \mathbb{N}$, does ...
Max Flow's user avatar
  • 193
4 votes
0 answers
134 views

Status of the Junta Problem (soft question)

Does the learning theory community in general believe that juntas can be learned in polynomial time? The naive algorithm works in quasi-polynomial time. MOS's paper shows how to solve the junta ...
zfkmz's user avatar
  • 187
12 votes
1 answer
824 views

What is the complexity of checking equivalence of two boolean formulae without NOT symbol?

Suppose I have two boolean formulae (propositions) $P_1$, and $P_2$ (can be assumed to be in CNF) over the same variables and such that there are no "NOT" symbols used. I.e. only conjunction and ...
wanderingmathematician's user avatar
-1 votes
1 answer
84 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 ...
dnn's user avatar
  • 1
5 votes
2 answers
374 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 ...
Andy's user avatar
  • 245
5 votes
0 answers
117 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 $...
Bartolinio's user avatar
4 votes
1 answer
434 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 $\...
Han Zhao's user avatar
3 votes
1 answer
223 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 ...
Andy's user avatar
  • 245
10 votes
1 answer
363 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$. ...
a3nm's user avatar
  • 9,527
4 votes
1 answer
283 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, ...
Andy's user avatar
  • 245
2 votes
0 answers
163 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 ...
madbeebop's user avatar
5 votes
0 answers
153 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 ...
user340082710's user avatar
8 votes
1 answer
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?
Turbo's user avatar
  • 13k

1
2 3 4 5