19
votes
Accepted
Boolean Functions Where Sensitivity Equals Block Sensitivity
Recently, I proved that s(f) = bs(f) for unate functions and read-once functions over the Boolean operators AND, OR and EXOR, and my paper including the results was accepted to TCS 2014.
(http://dx....
- 689
17
votes
Accepted
On the sensitivity conjecture?
From the paper: what is actually proven is, in Theorem 1.4,
$$
\forall f\colon\{0,1\}^n \to \{0,1\}, \qquad s(f) \geq \sqrt{\deg f} \tag{1}
$$
which cannot be improved (it is tight for some functions)....
- 4,341
15
votes
Do I have to give up the Law of the Excluded Middle in order to Learn $\lambda$-Calculus?
To me, your question seems analogous to saying "I've heard that non-Euclidean geometry requires me to give up Euclid's fifth axiom, which is very useful in many mathematical contexts." You don't have ...
- 251
14
votes
Accepted
Do I have to give up the Law of the Excluded Middle in order to Learn $\lambda$-Calculus?
You seem to be confusing several things here.
First of all, like Alexis said in her answer, I don't see why you would need to accept/reject the principles of a given logical theory in order to study ...
- 4,823
14
votes
Accepted
Has there been any progress in tightening the exponent in the result that polylog independence fools $AC_0$?
In his CCC'17 paper [1], Avishay Tal improved the bound to $$
\left(\log\frac{m}{\varepsilon}\right)^{O(d)}\,. \tag{1}
$$
You may want to check p.15:4 for a discussion. It also refers to (see Footnote ...
- 4,341
13
votes
Sensitivity-Block sensitivity conjecture - Implications
Here is what Scott Aaronson has to say on the subject:
What makes this interesting is that block-sensitivity is known to be polynomially related to a huge number of other interesting complexity ...
- 14.1k
13
votes
Accepted
What is the complexity of checking equivalence of two boolean formulae without NOT symbol?
Note that formulas using $\land$ and $\lor$ gates (and possibly the constants $0$ and $1$) are known as monotone.
The complexity of monotone formula equivalence depends on how complex formulas are ...
- 14.8k
11
votes
Random functions of low degree as a real polynomial
Here's an algorithm that beats the trivial attempts.
The following is a known fact (Exercise 1.12 in O'Donnell's book) : If $f:\{-1,1\}^n\to\{-1,1\}$ is a Boolean function which has degree $\le d$ as ...
- 353
11
votes
Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?
LMN theorem shows that if f is a boolean function$(f:\{-1,1\}^n \rightarrow \{-1,1\})$ computable by an $\text{AC}^0$ circuit of size M,
$$\sum_{S:|S|> k} \hat f(S)^{2} \leq 2^{-\Omega(k/(\log M)^{...
- 193
11
votes
Accepted
May Boolean circuits be exponentially more concise than Boolean formulae?
The circuit complexity of any boolean function of $n$ variables is at most $(1+o(1))2^n/n$, so a separation of between circuit and formula complexity of $\Omega(2^n)$ is not possible. This upper bound ...
- 18k
11
votes
Do I have to give up the Law of the Excluded Middle in order to Learn $\lambda$-Calculus?
Type theory is a mathematical theory in which we can do very many different things (set theory is like that as well). We can use type theory for computability, or homotopy theory, or use it to express ...
- 26.6k
11
votes
Accepted
Proper PAC learning VC dimension bounds
My thanks to Aryeh for bringing this question to my attention.
As others have mentioned, the answer to (1) is Yes, and the
simple method of Empirical Risk Minimization in $\mathcal{C}$ achieves
the ...
- 126
11
votes
Accepted
Sampling monotone Boolean functions
In [1], the paper where Propp & Wilson introduce the "coupling from the past" technique for MCMC sampling, they also outline a "heat bath algorithm" applicable to a certain kind of spin system ...
- 3,381
10
votes
Accepted
Representing boolean function by a polynomial
Any function which has non-zero correlation with parity has degree $n$. That is, if $$\sum_{x \in \{0,1\}^n} (-1)^{\sum_i x_i}f(x) \neq 0$$
then the unique multilinear expansion of $f$ contains the ...
- 14.1k
10
votes
Accepted
Evaluate boolean circuit on batch of similar inputs
I'd consider it unlikely that such a trick is easy to find and/or will give you significant gains, as it would give nontrivial satisfiability algorithms. Here's how:
First of all, while ostensibly ...
- 1,419
9
votes
Complexity class of sensitivity
[An alternative answer for $BS(f)$]
There is a paper related to this problem.
Scott Aaronson: Algorithms for Boolean Function Query Properties.
SIAM J. Comput. 32(5): 1140-1157 (2003)
The paper ...
- 689
9
votes
Accepted
a polynomial representation of boolean functions
Well done on your independent discovery.
This is a Hadamard matrix of Sylvester type, written in a different order. There is a massive literature on this topic. It is used in coding theory, ...
- 1,986
9
votes
Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture
Here's just a couple of observations I couldn't fit in a comment:
0) Added because the first answer was deleted: there is an interpretation of $H_n$, namely, indexing the rows and columns by $\{0,1\}^...
- 740
9
votes
Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture
An observation too long for a comment (and which also fits well with Jason Gaitonde's observation-too-long-for-comment):
As hinted at in the OQ, both of these can in fact be realized by a very simple ...
- 35.7k
8
votes
Do I have to give up the Law of the Excluded Middle in order to Learn $\lambda$-Calculus?
I agree with Alexis and Damiano, and there is another dimension to $\lambda$-calculus that is not often emphasised, because of the dominance of the Curry-Howard correspondence in thinking about the $\...
- 10.3k
8
votes
Accepted
variant of Critical SAT
It is clear that your language is in DP. In order to show that it is DP-hard, we will give a reduction from SAT-UNSAT to your language, which we can call CRIT-UNSAT. Given a pair of CNFs $(f,g)$, let $...
- 14.1k
8
votes
Average-case analogue of Small-bias Spaces
Below I show how to explicity construct an average-case $\varepsilon$-biased space on $n$ bits of size $O(1/\varepsilon)$.
In contrast, the best worst-case $\varepsilon$-biased spaces on $n$ bits ...
- 2,743
8
votes
Accepted
Is the basis of parity functions the only orthonormal basis for Boolean functions?
I don't think parities are the only orthonormal Boolean basis, for example Paley basis provides a Boolean orthonormal basis in some cases. It's natural to ask if such bases, interpreted as Boolean ...
- 4,011
7
votes
Accepted
Complexity class of sensitivity
For fixed $c$ the complexity is polynomial time. In fact, you can calculate $S(f)$ in polynomial time by just going over all inputs and calculating the pointwise sensitivity. This takes $O(n2^n)$ on a ...
- 14.1k
7
votes
Circuit complexity of Majority function
The proof (due to Miller and Preparata, 1975) that any symmetric function can be computed by circuits over {AND,OR,NOT} in logarithmic depth can be found, e.g., in Complexity of Boolean Functions by ...
7
votes
Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value
Here is a better bound on the sample complexity. (Although the computational complexity is still $n^k$.)
Theorem. Assume there exists a subcube $S$ of size $2^{n-k}$ such that $|\mathbb{E}_{x \in S}[...
- 2,743
7
votes
Why does Fourier analysis of Boolean functions "work"?
Here might be another take on this question.
Assuming the pseudo Boolean function is k-bounded, the Walsh polynomial
representation of the function can be decomposed into k subfunctions.
All of the ...
7
votes
Checking formulas with two quantifiers ($\forall \exists$) - 2QBF
I have read two papers related to this, one specifically related to 2QBF. The papers are the following:
Incremental Determinization, Markus N. Rabe and Sanjit Seshia, Theory and Applications of ...
- 209
7
votes
What is the VC Dimension of the $k-$Junta class
For the very limited situation in which $k=1$ and we're only interested in functions whose domain is $\{0,1\}^n$, the VC dimension is $\lfloor \log_2(n+1) + 1 \rfloor$.
The upper bound follows ...
- 1,419
6
votes
Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?
See also the recent paper of Daniel Kane and Ryan Williams, Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-2 and Depth-3 Threshold Circuits (STOC 2016).
Ryan describes the paper as ...
- 14.1k
Only top scored, non community-wiki answers of a minimum length are eligible