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,451
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 ...
- 5,273
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,451
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 ...
- 16.9k
11
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,429
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 ...
- 28.3k
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,382
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, ...
- 2,070
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\}^...
- 800
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 ...
- 36.9k
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 $\...
- 11.4k
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.3k
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,803
8
votes
Accepted
Is Circuit Minimization $P$-hard under logspace reductions?
The Circuit Minimization Problem you describe is also known as MCSP (the Minimum Circuit Size Problem), which has been the subject of quite a few papers recently. (I'm posting an answer to this ...
- 1,761
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
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
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
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,429
6
votes
Is a monotone boolean function monotone as a multilinear polynomial?
Yes.
Let $f : \{-1,1\}^n \to \mathbb{R}$, and let $F : [-1,1]^n \to \mathbb{R}$ be its multilinear extension. If $f$ is monotone, then so is $F$.
proof: Fix a variable index $i$; we'll show that $\...
- 1,429
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.3k
6
votes
Proper PAC learning VC dimension bounds
Your questions (1) and (2) are related. First, let's talk about proper PAC learning. It is known that there are proper PAC learners that achieve zero sample error, and yet require $\Omega(\frac{d}{\...
- 10.3k
6
votes
Accepted
Complexity of Maximizing Hamming Distances Below a Threshold
Lemma 1. The problem is NP-hard, by reduction from Max-2-SAT.
Proof sketch. The reduction is in two steps. Consider the variant of the problem in which $d$ is even and the coverage requirement is ...
- 9,595
5
votes
Proper PAC learning VC dimension bounds
To add to the currently accepted answer:
Yes. The $$O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$$
sample complexity upper bound holds for proper PAC learning as well (although it is ...
- 4,451
5
votes
Accepted
Basic property of boolean functions with restrictions
This is Corollary 3.22 of Analysis of Boolean Functions, by Ryan O'Donnell (2014). You may want to consult the proof in the book, or look directly at the online version (which has a different ...
- 4,451
5
votes
Accepted
Given a subset of of the hypercube and an affine transform of it, find the affine map
From D.W.'s comment, we see that your problem is equivalent to the same problem with $s=0$ (and with $d$ only increased by 1). The resulting problem is precisely the Linear Code Equivalence Problem ...
- 36.9k
5
votes
Accepted
Dual to hypercontractive inequality
I'm not sure that the statement you want is known to hold in full generality (if you look at O'Donnell's website, he remarks that what he stated in that survey is not in fact known to be true in full ...
- 800
5
votes
Accepted
Complexity of constructing minimum depth decision trees
I think I can see a fairly easy reduction from 3DM. Let $B=\{0^J\}$, i.e., it is a singleton set with the only zero element. The points of $A$ correspond to the points of the 3DM that are to be ...
- 13.9k
5
votes
Accepted
A boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$ is chosen at random from all $2^{2^n}$ such $f$. What do the Fourier coefficients look like?
Here's one way of attacking the problem.
Any boolean function $f: [2]^n \rightarrow [2]$ can be written as
\begin{equation}
f(\alpha) = \sum_{\beta \in [2]^n} \chi_{\beta}\delta_{\beta} (\alpha)
\end{...
- 234
Only top scored, non community-wiki answers of a minimum length are eligible