# Questions tagged [boolean-functions]

Questions about Boolean functions and their analysis

217 questions
Filter by
Sorted by
Tagged with
344 views

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{ ... 2 votes 0 answers 38 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 ... 0 votes 0 answers 31 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 ... 1 vote 0 answers 74 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 ... 3 votes 0 answers 95 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 ... 4 votes 1 answer 172 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 ... 1 vote 0 answers 43 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 ... 0 votes 1 answer 110 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&... 1 vote 1 answer 115 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 ... 0 votes 1 answer 152 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 ... 2 votes 1 answer 184 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 ... 2 votes 1 answer 134 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 ... 8 votes 1 answer 145 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 ... 7 votes 1 answer 178 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 ... 2 votes 0 answers 57 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, ... 0 votes 0 answers 91 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 ... 0 votes 0 answers 58 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 ... 2 votes 0 answers 95 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 ... 5 votes 0 answers 112 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 ... 3 votes 1 answer 167 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 ... 3 votes 0 answers 105 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 ... 2 votes 2 answers 318 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 ... 1 vote 1 answer 248 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 ... 8 votes 1 answer 223 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 ... 3 votes 1 answer 158 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 ... 4 votes 0 answers 86 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, ... 5 votes 1 answer 375 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" ... 3 votes 0 answers 109 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 ... 6 votes 1 answer 412 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 ... 7 votes 1 answer 380 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 ... 4 votes 0 answers 124 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 ... 11 votes 1 answer 718 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 ... -1 votes 1 answer 83 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 ... 4 votes 1 answer 270 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 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 ... 4 votes 1 answer 431 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 1 answer 215 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 ... 10 votes 1 answer 351 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 1 answer 279 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, ... 2 votes 0 answers 151 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 ... 5 votes 0 answers 145 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 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? 2 votes 0 answers 150 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 0 answers 284 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 ... 4 votes 1 answer 162 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 2 answers 356 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 ... 6 votes 0 answers 390 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 2 answers 732 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
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$ ...
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 ...