Timeline for List of proofs where existence through probabilistic method has not been constructivised
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 29, 2015 at 1:04 | comment | added | Turbo | @SashoNikolov thank you for the link. | |
| Dec 28, 2015 at 16:12 | comment | added | Sasho Nikolov | While there definitely are open questions about deterministically constructing matrices with the RIP property in polynomial time, I think this paper resolves the question of a deterministic JL lemma in time polynomial in $m$ cs.cmu.edu/~odonnell/papers/eio02.pdf. The issue with using this for constructing RIP matrices is that you would need it for an implicit $S$: the union of $k$-dimensional coordinate subspaces. | |
| S Dec 27, 2015 at 16:45 | history | answered | Paul Siegel | CC BY-SA 3.0 | |
| S Dec 27, 2015 at 16:45 | history | made wiki | Post Made Community Wiki by Paul Siegel |