Sunday, May 03, 2009

A Compendium of PPAD-complete problems

Motivated by my recent paper (joint work with Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng) and a suggestion of Noam Nisan, I created a compendium of PPAD-complete problems. Please let me know if you see any additions/corrections.

2 comments:

Suresh Venkatasubramanian said...

thanks ! might be too much work for you, but if it was a wikipedia page, then others could also link to descriptions of the problems, or even add descriptions of the problems.

are there also problems that are in limbo (like the HAM SANDWICH problem I had asked about), and are worth listing ?

Shiva Kintali said...

Suresh,

I was waiting the much-talked-about theoryWiki. It would be nice to have a theoryWiki for more organized theory content (like open problem garden). I don't know how far we are from having one :(

In the meanwhile, I will add a wikipedia entry soon. Regarding the problems in limbo, I will add a section about open problems in PPAD.