# Tag Info

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....
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

### 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
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
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

### 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
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

### 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

• 14.1k
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

### 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 ...
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

• 10.3k
Accepted

• 2,743

### 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 ...

### 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
### 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 ...