Name
Abstract | ||
|---|---|---|
For every n-point subset X of Euclidean space and target distortion 1+eps for 0 l_2^m where f(x) = Ax for A a matrix with m rows where (1) m = O((log n)/eps^2), and (2) each column of A is sparse, having only O(eps m) non-zero entries. Though the constructions given for such A in (Kane, Nelson, J. ACM 2014) are simple, the analyses are not, employing intricate combinatorial arguments. We here give two simple alternative proofs of their main result, involving no delicate combinatorics. One of these proofs has already been tested pedagogically, requiring slightly under forty minutes by the third author at a casual pace to cover all details in a blackboard course lecture. |
Year | Venue | Field |
|---|---|---|
2018 | SOSA@SODA | Row,Discrete mathematics,Binary logarithm,Combinatorics,Computer science,Matrix (mathematics),Euclidean space,Mathematical proof,Distortion |
DocType | Citations | PageRank |
Conference | 1 | 0.36 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael B. Cohen | 1 | 183 | 11.73 |
| T. S. Jayram | 2 | 1373 | 75.87 |
| Jelani Nelson | 3 | 667 | 34.46 |