MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Relative in what sense? – Andrej Bauer Jul 30 '10 at 9:01
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. – Kaveh Jul 31 '10 at 22:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.