3
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ I may be missing something, but doesn't parity exhibit that the answer to 1 is negative? $\endgroup$
    – Emil Jeřábek
    Nov 24, 2015 at 11:53
  • $\begingroup$ @EmilJeřábek : thanks, you're right. I have edited the question. $\endgroup$
    – verifying
    Nov 24, 2015 at 23:42
  • 1
    $\begingroup$ 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? $\endgroup$
    – Sasho Nikolov
    Nov 25, 2015 at 3:53
  • 1
    $\begingroup$ @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 ...) $\endgroup$
    – verifying
    Nov 25, 2015 at 8:13
  • 1
    $\begingroup$ Avishay Tal has an alternative proof for the shrinkage exponent over the de Morgan basis with slightly better bounds: eccc.hpi-web.de/report/2014/048. $\endgroup$
    – Yuval Filmus
    Nov 25, 2015 at 9:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.