Timeline for How feasible is it to prove Kazhdan's property (T) by a computer?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 16, 2022 at 21:40 | history | edited | Stefan Kohl♦ | CC BY-SA 4.0 |
Simple edit to allow a user to undo an accidental downvote.
|
| Nov 16, 2022 at 8:49 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
http -> https (the question was bumped anyway)
|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jan 14, 2014 at 0:39 | comment | added | Narutaka OZAWA | David Speyer, thank you for your insight. François G. Dorais, thank you for your clarification. | |
| Jan 14, 2014 at 0:30 | comment | added | David E Speyer | Right. One should add that, by Tarski's theorem, it is decidable whether an SDP is solvable but, according to the Handbook of Semidefinite Programming books.google.com/… "Given an SDP ... there is no polynomial time algorithm to decide whether it is feasible or not." | |
| Jan 13, 2014 at 23:56 | comment | added | François G. Dorais | @NarutakaOZAWA: SDP will solve the problem to a prescribed accuracy $\varepsilon$. If the output is a positive number less than $\varepsilon$ then the true solution could still be $0$; more accuracy is needed to determine whether the true answer is positive or zero. It's only if the required precision is known in advance that this gives a decision procedure. | |
| Jan 13, 2014 at 23:47 | comment | added | Narutaka OZAWA | @François G. Dorais: How does SDP work? First of all, $r\le0$ always solves the equation. When the computer says there's a solution $r>0$, does it really mean that? Or do we need enough margin between $r$ and $0$ to be sure? Anyway, we should be able to verify it working in ${\mathbb Z}[\Gamma]$, shouldn't we? | |
| Jan 13, 2014 at 23:31 | comment | added | François G. Dorais | The complexity of SDP depends on the size of the problem and the degree of accuracy desired. The first is correlated to the size of the set $T$ and the second depends on how far the "optimal $r$" is from zero. Is there a way to estimate how big $r$ would be if there is a positive one? | |
| Jan 13, 2014 at 20:47 | history | edited | David E Speyer | CC BY-SA 3.0 |
edited body
|
| Jan 13, 2014 at 20:07 | history | answered | David E Speyer | CC BY-SA 3.0 |