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....
user avatar
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)....
user avatar
  • 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 ...
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 ...
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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)^{...
user avatar
  • 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 ...
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 ...
user avatar
  • 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 ...
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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\}^...
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 ...
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 $\...
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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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}[...
user avatar
  • 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 ...
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 ...
user avatar
  • 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 ...
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 ...
user avatar
  • 14.1k

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