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)....
Clement C.'s user avatar
  • 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 ...
Alexis's user avatar
  • 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 ...
Damiano Mazza's user avatar
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 ...
Clement C.'s user avatar
  • 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 ...
Emil Jeřábek's user avatar
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 ...
Andrew Morgan's user avatar
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 ...
Andrej Bauer's user avatar
  • 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 ...
S. Hanneke's user avatar
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 ...
mhum's user avatar
  • 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, ...
kodlu's user avatar
  • 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\}^...
Jason Gaitonde's user avatar
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 ...
Joshua Grochow's user avatar
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 $\...
Martin Berger's user avatar
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 $...
Yuval Filmus's user avatar
  • 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 ...
Thomas's user avatar
  • 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 ...
Eric Allender's user avatar
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 ...
Mahdi Cheraghchi's user avatar
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 ...
Pushpa's user avatar
  • 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 ...
Darrell Whitley's user avatar
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 ...
Andrew Morgan's user avatar
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 $\...
Andrew Morgan's user avatar
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 ...
Yuval Filmus's user avatar
  • 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}{\...
Aryeh's user avatar
  • 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 ...
Neal Young's user avatar
  • 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 ...
Clement C.'s user avatar
  • 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 ...
Clement C.'s user avatar
  • 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 ...
Joshua Grochow's user avatar
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 ...
Jason Gaitonde's user avatar
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 ...
domotorp's user avatar
  • 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{...
Pedro Juan Soto's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible