The term "Ironic complexity" was coined by Scott Aaronson for the stuff Ryan Williams does in the area of complexity theory. Could anyone tell me what kind of problems and approaches does Ryan Williams work upon? And is there a survey or course on it for self-study?

  • $\begingroup$ Check out Ryan Williams' homepage as well as this. $\endgroup$ – dkaeae Feb 21 at 16:34
  • $\begingroup$ Also, "ironic complexity" is hardly a "term" since apparently only Scott Aaronson uses it. $\endgroup$ – dkaeae Feb 21 at 16:35
  • $\begingroup$ It's supposed to be an ironic term. $\endgroup$ – Yuval Filmus Feb 21 at 19:06
  • 1
    $\begingroup$ Good sources are Scott's survey and Ryan's papers and talks. $\endgroup$ – Yuval Filmus Feb 21 at 19:08

Here is a quote from Scott Aaronson's survey on the P vs NP question, in which he coined this term:

There is one technique that has had some striking recent successes in proving circuit lower bounds, and that bypasses the natural proofs, relativization, and algebrization barriers. This technique might be called “ironic complexity theory.” It uses the existence of surprising algorithms in one setting to show the nonexistence of algorithms in another setting. It thus reveals a “duality” between upper and lower bounds, and reduces the problem of proving impossibility theorems to the much better-understood task of designing efficient algorithms.

The survey contains some pointers which you might want to look at.

Ryan Williams has given a series of two talks on this recently at the Simons institute: part 1 and part 2.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.