Timeline for Probability measure on the boolean cube with small support and small Fourier transform
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 31, 2022 at 21:30 | comment | added | Mikael de la Salle | @J.G I would like to acknowledge your help in a paper that I am finishing to write. I can simply thank "MO user J.G", but if you agree to disclose your identity, I can thank you with your real-life identity. You can write me an email if you wish. | |
| Jan 25, 2022 at 16:40 | vote | accept | Mikael de la Salle | ||
| Jan 25, 2022 at 15:57 | comment | added | Jason Gaitonde | @MikaeldelaSalle just made it into an answer. Very glad to have helped! | |
| Jan 25, 2022 at 15:57 | answer | added | Jason Gaitonde | timeline score: 7 | |
| Jan 24, 2022 at 22:22 | comment | added | Mikael de la Salle | @J.G you are correct, thanks a lot, this is precisely what I was looking for. If you make your comment into an answer, I will accept it. | |
| Jan 24, 2022 at 19:54 | comment | added | Jason Gaitonde | I think what you're looking for is an $\epsilon$-biased space (where in your case, $\epsilon=1/2$) (i.e. the expectation of any nontrivial parity function with respect to the distribution is at most $\epsilon$ in absolute value). To my knowledge, the best current construction is by Ta-Shma (Theorem 1 of eccc.weizmann.ac.il/report/2017/041) and gives a set of size $O(N/\epsilon^{2+o(1)})$ which is near-optimal, so should be what you need. The references there might give earlier and simpler constructions giving $O(N)$ for $\epsilon = 1/2$ from better codes. | |
| Jan 24, 2022 at 17:41 | history | edited | Mikael de la Salle | CC BY-SA 4.0 |
Fixed typo on the degree of polynomials
|
| Jan 24, 2022 at 17:05 | history | edited | Mikael de la Salle | CC BY-SA 4.0 |
added 13 characters in body
|
| Jan 24, 2022 at 16:47 | history | edited | Mikael de la Salle | CC BY-SA 4.0 |
Added details and a proof of my claim in Reed-Muller codes, as requested in the comments.
|
| Jan 24, 2022 at 15:31 | comment | added | kodlu | What is the order of the Reed-Muller codes that you used for that estimate. Can you include details? | |
| Jan 24, 2022 at 11:22 | history | edited | Thomas Sauvaget | CC BY-SA 4.0 |
Fixed a typo in Hoeffding
|
| Jan 24, 2022 at 10:16 | history | edited | Mikael de la Salle |
changed tags
|
|
| Jan 24, 2022 at 9:54 | history | asked | Mikael de la Salle | CC BY-SA 4.0 |