Timeline for Counting roots: multidimensional Sturm's theorem
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 24, 2012 at 8:15 | answer | added | Markus Schweighofer | timeline score: 3 | |
| Oct 29, 2010 at 8:43 | comment | added | Boris Bukh | Is it NP-hard in fixed dimension, though? | |
| Oct 28, 2010 at 22:13 | comment | added | alex | NP-hardness is one barrier for this kind of theorem, since it is NP-hard to check if a multi-variable polynomial has at least one root. It is still NP-hard if you restrict yourself to polynomials which have finitely many roots all of which must be in $[0,1]^n$. So any counting algorithm would take at least exponential time in $n$. | |
| Oct 28, 2010 at 19:30 | vote | accept | Boris Bukh | ||
| Oct 28, 2010 at 15:30 | answer | added | Thierry Zell | timeline score: 9 | |
| Oct 28, 2010 at 15:17 | answer | added | David E Speyer | timeline score: 10 | |
| Oct 28, 2010 at 14:37 | history | asked | Boris Bukh | CC BY-SA 2.5 |