Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Institute of Advanced Study

Expand Messages
  • Lance Fortnow
    The Institute will be quite a complexity powerhouse this year. In addition to IAS fixtures Wigderson and Razborov, visiting are Russell Impagliazzo, Manindra
    Message 1 of 1 , Sep 4, 2003
    • 0 Attachment
      The Institute will be quite a complexity powerhouse this year. In addition to IAS fixtures Wigderson and Razborov, visiting are Russell Impagliazzo, Manindra Agrawal (with his students Kayal and Saxena at Princeton) and postdocs Boaz Barak, Subhash Khot, Ryan O'Donnell and Nate Segerland. These are just the ones I met yesterday during a short visit several weeks before their semester officially begins. We'll expect great things from them.

      Here is a question we thought about yesterday, posed by Ryan O'Donnell and ultimately settled by Boaz Barak:

      Exhibit an NP-complete language L, such that for all lengths n≥1, L contains exactly half (2n-1) of the strings of length n.

      Think about it. I'll post the proof next week.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 9/4/2003 01:31:11 PM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.