Questions tagged [boolean-functions]

Questions about Boolean functions and their analysis

Filter by
Sorted by
Tagged with
33 votes
2 answers
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 ...
user avatar
23 votes
4 answers
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 ...
user avatar
  • 21.3k
11 votes
3 answers
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 $\...
user avatar
7 votes
2 answers
653 views

Communication lower bounds for partial boolean functions

There are well known techniques for proving lower bounds on the communication complexity of boolean functions, like fooling sets, the rank of the communication matrix, and discepancy. 1) How do we ...
user avatar
6 votes
2 answers
829 views

Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?

Let $f: \{-1,1\}^n \rightarrow \{-1,1\}$ be a Boolean function. The Fourier expansion of $f$ is $$f(T) = \sum_{S \subseteq [n]} \widehat{f}(S)\ \chi_S(T)$$ where $\widehat{f}(S)$ are real numbers ...
user avatar
  • 1,984
66 votes
3 answers
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 ...
user avatar
23 votes
4 answers
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 ...
user avatar
21 votes
1 answer
433 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 ...
user avatar
  • 1,897
15 votes
1 answer
865 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 ...
user avatar
  • 21.3k
12 votes
1 answer
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 ...
user avatar
  • 1,334
13 votes
3 answers
5k 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 ...
user avatar
  • 639
16 votes
2 answers
318 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 $\...
user avatar
5 votes
1 answer
405 views

Complexity of multi-linear polynomial computing Boolean function

Let $f:\{0,1\}^{n}\longmapsto\{0,1\}$ be a Boolean function. As usual, let $C(f)$ denote circuit complexity of $f$, i.e, the size of the smallest Boolean circuit computing $f$. As we know that every ...
user avatar
19 votes
2 answers
947 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 ?
user avatar
  • 523
14 votes
3 answers
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 ...
user avatar
  • 10.4k
7 votes
2 answers
339 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 ...
user avatar
7 votes
2 answers
347 views

Boolean functions with exponential size OBDD representation in all orders except one order?

Are there boolean functions with exponential size OBDD representation in all orders except one order? ...exponential size in all orders except very few orders? The exceptional orders should be ...
user avatar
  • 343
6 votes
1 answer
630 views

Lower bounds for Polynomials computing the boolean functions

Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x_{1},...,x_{n})$, where $x_{1},...,x_{n}$ may be integer, finite fields, or other fields. One of the most ...
user avatar
  • 201
6 votes
0 answers
306 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 ...
user avatar
6 votes
0 answers
90 views

Representing boolean function by a rational function

What is known about the separation of minimal degrees of polynomials and that of rational functions that represent boolean functions? What is a good reference for the topic?
user avatar
  • 12.5k
1 vote
0 answers
61 views

Candidate Boolean Function with efficient rational representation compared to polynomial representation

Let $x_1,x_2,\dots x_n$ be literals. Let $P(x_1,x_2,\dots,x_n)$ be a boolean function. Let $d$ be the smallest degree of $f(x_1,x_2,\dots,x_n)\in \mathbb R[x_1,x_2,\dots,x_n]$ that represents $P(x_1,...
user avatar
  • 12.5k