15
$\begingroup$

This post is about Natural Proofs barrier in computational complexity.

There are two recent papers related to this. They are:

  1. Amplifying lower bounds by means of self-reducibility by Eric Allender and Michal Koucký,

  2. Almost-natural proofs by Timothy Chow.

Alexander Razborov mentioned them at the end of his talk in the first Barriers Workshop at IAS in 2009. The video of his talk is available here. He mentioned that a possible way to respond to these would be to make the largeness condition relative. So here is my question:

Has there been any progress on this?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Relative in what sense? $\endgroup$
    – Andrej Bauer
    Commented Jul 30, 2010 at 9:01
  • $\begingroup$ As far as I understand, he was saying that one should redefine the largeness to be relative to the class of functions being attacked. His comments were very brief (last 5min of his talk). I will add a link to the video of his talk to the post. $\endgroup$
    – Kaveh
    Commented Jul 31, 2010 at 22:25

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .