Questions tagged [boolean-functions]
Questions about Boolean functions and their analysis
19
questions
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 ...
23
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 ...
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 $\...
7
votes
2answers
640 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 ...
6
votes
2answers
815 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 ...
65
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 ...
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 ...
21
votes
1answer
420 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 ...
15
votes
1answer
846 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 ...
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 ...
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 ...
16
votes
2answers
311 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 $\...
5
votes
1answer
387 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 ...
19
votes
2answers
933 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 ?
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 ...
7
votes
2answers
337 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 ...
7
votes
2answers
341 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 ...
6
votes
0answers
294 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 ...
6
votes
1answer
615 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 ...
