Timeline for Cut norm versus $l_1$ norm
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 3, 2020 at 17:52 | comment | added | alesia | I'm confident about the square root behavior for tweaked Hadamard matrices (based on spectral radius), but didn't fully checked optimality | |
| May 3, 2020 at 17:45 | comment | added | Ilya Bogdanov | That's my feeling as well, but have you checked that? | |
| May 3, 2020 at 17:36 | comment | added | alesia | @IlyaBogdanov You'd need to fix the zero sum row constraint as well, but I think this would give $\Theta(\sqrt n)$. It sounds plausible that this behavior is optimal, but I'm not sure. | |
| May 3, 2020 at 17:27 | comment | added | Ilya Bogdanov | What bounds provide Hadamard matrices, if you change diagonal elements to zeroes? (There should be many pluses and minuses on the diagonal.) | |
| May 3, 2020 at 17:12 | answer | added | Vartan Choulakian | timeline score: 1 | |
| Apr 28, 2020 at 10:44 | answer | added | Vartan Choulakian | timeline score: 0 | |
| Dec 11, 2019 at 3:01 | comment | added | alesia | Also I came across Grothendieck inequality and the related SDP relaxation of the cut polytope ("elliptope"), which could help as well | |
| Dec 11, 2019 at 2:57 | comment | added | alesia | I had tried that but very little is known about the extreme points, there are papers on very specific families but that's all. Meanwhile I found that Hadamard matrices are close to being examples of what I want although they don't exactly match the conditions | |
| Dec 11, 2019 at 2:53 | comment | added | Iosif Pinelis | Have you tried to find the extreme points of the set of matrices in $K$ with cut norm $1$? Then you can maximize $\sum_{ij}|M_{ij}|$ "just" over such extreme matrices. | |
| Dec 8, 2019 at 23:05 | history | edited | alesia | CC BY-SA 4.0 |
edited body
|
| Dec 8, 2019 at 15:54 | history | asked | alesia | CC BY-SA 4.0 |