<p>Håstad has shown that the shrinkage exponent of boolean formulas over the De Morgan basis is 2. In other words, if one keeps each variable of the formula alive with probability $p$ and restricts it with a uniform random bit otherwise, then the resulting formula can be shrunk by a factor of roughly $p^2$ in such a way that it computes the same function. This fact can be used to prove a $\Omega(n^2)$ lower obund for the parity on $n$ bits, and a 
$\Omega(n^{3-o(1)})$ lower bound for Andreev's function.</p>

<p>I have the following questions:</p>

<ol>
<li><p>The shrinkage exponent of a formula over the full binary basis is 1 (consider for instance the parity function). Is there some relaxation of the notion of shrinkage exponent which is greater than 1 for formulas over the full binary basis? </p></li>
<li><p>Has such a relaxation of the notion of shrinkage exponent been used to obtain lower bounds? </p></li>
</ol>

CC BY-SA 3.0
2015-11-24T11:53:48.640Z
I may be missing something, but doesn't parity exhibit that the answer to 1 is negative?
Emil Jeřábek
CC BY-SA 3.0
2015-11-24T23:42:38.827Z
@EmilJeřábek : thanks, you're right. I have edited the question.
verifying
CC BY-SA 3.0
2015-11-25T03:53:27.333Z
I am not an expert, but the only lower bound method I am aware of for formulas over the full binary basis is Nechiporuk's method. I am not sure what relaxation you have you in mind, but if you mean something useful in proving lower bounds, isn't it going to be hopeless for the parity function, since it has $O(n)$ size formulas over the full basis?
Sasho Nikolov
CC BY-SA 3.0
2015-11-25T08:13:52.643Z
@SashoNikolov The kind of relaxed shrinkage exponent that I have in mind is something that diminishes the influence of parity. For instance, one could define a notion of random shrinkage exponent, i.e., the shrinkage exponent of a random function. Note that the usual shrinkage exponent is defined as the minimum "shrinkage exponent" where the minimum is taken over all possible functions. If instead of minimum over all functions we take the average, I believe this would be a different measure. (continues below ...)
verifying
CC BY-SA 3.0
2015-11-25T08:17:14.980Z
Note that the only property of parity that is used in lower bounds is that parity is not killed upon restricting many of its variables. There may be many functions with this property.
verifying
CC BY-SA 3.0
2015-11-25T09:30:45.887Z
Avishay Tal has an alternative proof for the shrinkage exponent over the de Morgan basis with slightly better bounds: http://eccc.hpi-web.de/report/2014/048/.
Yuval Filmus
<circuit-complexity><boolean-formulas>
Shrinkage Exponent of Formulas over the Full Binary Basis
verifying
# Shrinkage Exponent of Formulas over the Full Binary Basis

(Asked by: username_0 on 2015-11-24)

Håstad has shown that the shrinkage exponent of boolean formulas over the De Morgan basis is 2. In other words, if one keeps each variable of the formula alive with probability $p$ and restricts it with a uniform random bit otherwise, then the resulting formula can be shrunk by a factor of roughly $p^2$ in such a way that it computes the same function. This fact can be used to prove a $\Omega(n^2)$ lower obund for the parity on $n$ bits, and a
$\Omega(n^{3-o(1)})$ lower bound for Andreev's function.

I have the following questions:

1. The shrinkage exponent of a formula over the full binary basis is 1 (consider for instance the parity function). Is there some relaxation of the notion of shrinkage exponent which is greater than 1 for formulas over the full binary basis?
2. Has such a relaxation of the notion of shrinkage exponent been used to obtain lower bounds?

**Tags:** circuit-complexity, boolean-formulas
> **Comments:**
> **username_1**: I may be missing something, but doesn't parity exhibit that the answer to 1 is negative?  
> **username_0**: @EmilJeřábek : thanks, you're right. I have edited the question.  
> **username_2**: I am not an expert, but the only lower bound method I am aware of for formulas over the full binary basis is Nechiporuk's method. I am not sure what relaxation you have you in mind, but if you mean something useful in proving lower bounds, isn't it going to be hopeless for the parity function, since it has $O(n)$ size formulas over the full basis?  
> **username_0**: @SashoNikolov The kind of relaxed shrinkage exponent that I have in mind is something that diminishes the influence of parity. For instance, one could define a notion of random shrinkage exponent, i.e., the shrinkage exponent of a random function. Note that the usual shrinkage exponent is defined as the minimum "shrinkage exponent" where the minimum is taken over all possible functions. If instead of minimum over all functions we take the average, I believe this would be a different measure. (continues below ...)  
> **username_0**: Note that the only property of parity that is used in lower bounds is that parity is not killed upon restricting many of its variables. There may be many functions with this property.  
> **username_3**: Avishay Tal has an alternative proof for the shrinkage exponent over the de Morgan basis with slightly better bounds: http://eccc.hpi-web.de/report/2014/048/.  

---

## 0 answers

