Questions tagged [boolean-functions]

Questions about Boolean functions and their analysis

Filter by
Sorted by
Tagged with
64
votes
3answers
7k views

Why does Fourier analysis of Boolean functions "work"?

Over the years I have gotten used to seeing many TCS theorems proved using discrete Fourier analysis. The Walsh-Fourier (Hadamard) transform is useful in virtually every subfield of TCS, including ...
33
votes
2answers
1k views

Cohomological approach to boolean complexity

A few years ago, there was some work by Joel Friedman relating lower circuit bounds to Grothendieck cohomology (see papers: http://arxiv.org/abs/cs/0512008, http://arxiv.org/abs/cs/0604024). Has this ...
29
votes
1answer
2k views

Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates

Let $f$ be a Boolean function and let's think about f as a function from $\{-1,1\}^n$ to $\{ -1,1 \}$. In this language the Fourier expansion of f is simply the expansion of f in terms of square free ...
26
votes
2answers
841 views

What is the complexity of distinguishing a true Fourier spectra from a fake one?

A $PH$ machine is given oracle access to a random Boolean function $f:\{0,1\}^n \to \{ -1,1 \}$ , and two Fourier spectra $g$ and $h$. The Fourier spectra of a function $f$ is defined as $F:\{0,1\}^...
23
votes
4answers
2k views

Social choice, arrow's theorem and open problems ?

Last few months I started to lecture myself on social choice, arrow's theorem and related results. After reading about the seminal results, I asked myself about what happens with partial order ...
23
votes
2answers
692 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{...
22
votes
4answers
1k views

Monotone arithmetic circuits

The state of our knowledge about general arithmetic circuits seems to be similar to the state of our knowledge about Boolean circuits, i.e. we don't have good lower-bounds. On the other hand we have ...
21
votes
1answer
415 views

Random functions of low degree as a real polynomial

Is there a (reasonable) way to sample a uniformly random boolean function $f:\{0,1\}^n \to \{0,1\}$ whose degree as a real polynomial is at most $d$? EDIT: Nisan and Szegedy have shown that a ...
19
votes
2answers
925 views

Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?

Are all the functions whose fourier weight is concentrated on the small sized sets(or terms with low degree) computed by $\mathsf{AC}^0$ circuits ?
19
votes
2answers
1k views

Linearly independent Fourier coefficients

A basic property of vector spaces is that a vector space $V \subseteq \mathbb{F}_2^n$ of dimension $n-d$ can be characterized by $d$ linearly independent linear constraints - that is, there exist $d$ ...
18
votes
2answers
487 views

Uses of XORification

XORification is the technique to make a Boolean function or formula harder by replacing every variable $x$ by the XOR of $k\geq 2$ distinct variables $x_1 \oplus \ldots \oplus x_k$. I am aware of ...
18
votes
0answers
425 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|+...
17
votes
2answers
488 views

An extension of the noise operator

In a problem I am currently working on, an extension of the noise operator arises naturally, and I was curious whether there has been prior work. First let me revise the basic noise operator $T_{\...
17
votes
1answer
3k views

Boolean Functions Where Sensitivity Equals Block Sensitivity

Some of the work on sensitivity vs. block sensitivity has been aimed at examining functions with as large a gap as possible between $s(f)$ and $bs(f)$ in order to resolve the conjecture that $bs(f)$ ...
16
votes
2answers
785 views

Robustness of splitting a junta

We say that a Boolean function $f: \{0,1\}^n \to \{0,1\}$ is a $k$-junta if $f$ has at most $k$ influencing variables. Let $f: \{0,1\}^n \to \{0,1\}$ be a $2k$-junta. Denote the variables of $f$ by $...
16
votes
2answers
309 views

On the status of learnability inside $\mathsf{TC}^0$

I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside $\...
16
votes
1answer
481 views

Can you decide equivalence for monotone Boolean expressions that do not contain negation in PTIME?

Is the following problem in PTIME, or coNP-hard: Given two Boolean expressions $e_1$ and $e_2$ in variables $x_1,\dots,x_n$, without negation (ie, the expressions are entirely built up via $\wedge$ ...
16
votes
1answer
273 views

Which monotone Boolean functions are representable as thresholds on sums?

I will introduce my problem with an example. Say you are designing an exam, which consists of a certain set of $n$ independent questions (that the candidates can get either right or wrong). You want ...
15
votes
1answer
837 views

Random monotone function

In Razborov-Rudich's Natural Proofs paper, page 6, in the part they discuss that there are "strong lowerbounds proofs against monotone circuit models" and how they fit into the picture, there are the ...
15
votes
0answers
600 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 ...
14
votes
3answers
1k views

Checking formulas with two quantifiers ($\forall \exists$) - 2QBF

SAT solvers give a powerful way to check the validity of a boolean formula with one quantifier. For instance, to check the validity of $\exists x . \varphi(x)$, we can use a SAT solver to determine ...
14
votes
1answer
511 views

Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?

Result 1: Linial-Mansour-Nisan theorem says that the fourier weight of the functions computed by the $\mathsf{AC}^0$ circuits is concentrated on the subsets of small size with high probability. ...
14
votes
1answer
511 views

Beigel-Tarui transformation of ACC cricuits

I am reading the appendix about ACC lower bounds for NEXP in Arora and Barak's Computational Complexity book. http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf One of the key lemmas is a ...
14
votes
1answer
446 views

Expected minimum influence of a random Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$

For a Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$, the influence of the $i$th variable is defined as $$ \operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus ...
14
votes
0answers
325 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, ...
14
votes
0answers
312 views

Sign patterns for Fourier coefficients of Boolean functions

Given a sequence of real numbers $(a_i)$, the sign-pattern sequence $(s_i)$ is defined by $s_i = +$ if $a_i \geq 0$ and $s_i = -$ otherwise. For a boolean function $f: \{0,1\}^n \to \{0,1\}$, ...
13
votes
3answers
4k views

Circuit complexity of Majority function

Let $f: \{0,1\}^n \to \{0,1\}$ be the majority function, i.e. $f(x) = 1$ if and only if $\sum_{i = 1}^n x_i > n/2$. I was wondering if there was a simple proof of the following fact (by "simple" I ...
13
votes
2answers
444 views

Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?

There are several well-known $\mathsf{AC^0}$ circuit size lower-bound results based on random restrictions and the Switching Lemma. Can we develop a Switching Lemma result to prove a size lower-bound ...
13
votes
1answer
492 views

Hardness of noisy Boolean functions

Let $f$ be a Boolean function of $n$ Boolean variables. Let $g(x)=T_\epsilon (f) (x)$ be the expected value of $f(y)$ when $y$ is obtained from $x$ by flipping each coordinate with probability $\...
13
votes
1answer
548 views

Reference Request: Submodular Minimization and Monotone Boolean Functions

Background: In machine learning, we often work with graphical models to represent high dimensional probability density functions. If we discard the constraint that a density integrates (sums) to 1, ...
13
votes
0answers
229 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 ...
13
votes
0answers
428 views

How can one find the "hard" probability distribution on the input for recursive boolean functions?

Update: Since, it seems there is no progress regarding this question, any idea, conjecture, hunch, or advice is welcome. For example, are there any partial or incomplete results? What are the main ...
12
votes
2answers
1k views

Sensitivity-Block sensitivity conjecture - Implications

Let $f$ be a boolean function with sensitivity $s(f)$ and block sensitivity $bs(f)$. The Sensitivity-Block sensitivity conjecture conjecture states that there is a $c>0$ such that $\forall f,\mbox{...
12
votes
1answer
732 views

The entropy of a convolution over the hypercube

Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...
12
votes
0answers
276 views

Computing $\operatorname{MAJ}_n$ by $\operatorname{MAJ}_m$ in depth 2

Can the majority of $n$ bits be computed by a depth 2 formula all of whose gates compute the majority of $m$ bits where $m=O(n^c)$ for a constant $c<1$? Such a formula contains $m+1$ gates and $m^2$...
11
votes
3answers
1k 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 $\...
11
votes
1answer
3k views

Complexity of converting a boolean circuit to a boolean formula

Given a boolean circuit $C$ on $n$ variables (which uses just NOT,AND and OR gates), what is the most efficient way to extract the boolean formula represented by the circuit? Is there a polytime ...
11
votes
1answer
264 views

Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value

Here is a problem with a similar flavor to learning juntas: Input: A function $f: \{0,1\}^n \rightarrow \{-1,1\}$, represented by a membership oracle, i.e. an oracle that given $x$, returns $f(x)$. ...
10
votes
1answer
514 views

Proper PAC learning of 2-DNF under uniform distribution

What is the state of art result about query complexity of proper PAC learning 2-DNF formulas with sample queries and under uniform distribution? Or any non-trivial bound on it? Because I am not ...
10
votes
1answer
332 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,...
10
votes
2answers
2k views

Representing boolean function by a polynomial

Supposing we have a boolean function from $f:\{0,1\}^n\rightarrow\{0,1\}$. It is clear that a real multivariate polynomial $p(x)$ such that $f(x)=p(x)$ on $x\in\{0,1\}^n$ can be multilinear. What are ...
10
votes
1answer
287 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$. ...
10
votes
0answers
440 views

Relation beween approximate degree of a function and its Fourier coefficient.

Consider a Boolean function $f:\{0,1\}^n\to\{0,1\}$. The degree of the function $d$ has a clear meaning in term of its Fourier coefficients, there are no weight on coefficient of degree higher than $d$...
10
votes
0answers
440 views

Expectation of Gowers norm

This was an assignment problem in a course on analytics combinatorics that I had taken this semester. Here is the problem: Let $\mathbf{F}$ be the set of boolean functions, $f: \{0,1\}^n \rightarrow \...
10
votes
0answers
282 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 ...
9
votes
1answer
212 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 ...
9
votes
1answer
299 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 ...
9
votes
1answer
318 views

The entropy of a noisy distribution

Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$ such that $$\forall x\in \mathbb{Z}_2^n \quad f(x) \in \left\{\frac{1}{2^n}, \frac{2}{2^n}, \ldots, \frac{2^n}{2^n} \right\},$$ and $f$ is a ...
9
votes
1answer
719 views

Lower bounds on the Threshold function

In decision tree complexity of a boolean function, a very well know lower bound method is to find a (approximate) polynomial that represents the function. Paturi gave a characterization for symmetric ...
9
votes
1answer
189 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 ...