William Hird
  • Member for 9 years, 4 months
  • Last seen more than 1 year ago
Advanced techniques for determining complexity lower bounds
7 votes

Manindra Agrawal has a nice paper "Proving Lower Bounds via Psuedorandom Generators". This might be considered a "dark horse" in the running to prove lower bounds but the paper is interesting.

View answer
Are there any known NP problems which are conjectured to be exponentially hard on average?
6 votes

There are several psuedorandom number generators that we have no polynomial time algorithms for breaking. I guess you could consider them to be hard on average cases. Check out the generators at www....

View answer
What videos should everybody watch?
0 votes

The Richard Feynman YouTube video on magnets. Revealing how one of the greatest physicists of the 20th century cannot explain the force of magnetism (action at a distance) in terms of a simple ...

View answer