Questions tagged [boolean-functions]
Questions about Boolean functions and their analysis
21
questions
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 ...
- 2,786
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 ...
- 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 $\...
- 251
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 ...
- 3,270
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 ...
- 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 ...
user887
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 ...
- 3,043
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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 $\...
- 31.7k
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 ...
- 717
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 ?
- 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 ...
- 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 ...
- 173
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 ...
- 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 ...
- 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 ...
- 2,724
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?
- 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,...
- 12.5k