Timeline for What is the degree of a symmetric boolean function?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Mar 15, 2023 at 6:58 | history | suggested | The Amplitwist | CC BY-SA 4.0 |
fixed broken link to springerlink.com; added zbMATH review links in tooltips; added DOI of another paper; added link to darij's comment
|
| Mar 15, 2023 at 5:03 | review | Suggested edits | |||
| S Mar 15, 2023 at 6:58 | |||||
| Sep 3, 2011 at 18:43 | comment | added | Gerhard Paseman | And here I was looking at p being 1+prime because I thought the light was better. Gerhard "Ask Me About Missing Keys" Paseman, 2011.09.03 | |
| Sep 3, 2011 at 8:03 | vote | accept | Shir | ||
| Sep 2, 2011 at 11:04 | history | edited | Gjergji Zaimi | CC BY-SA 3.0 |
added 164 characters in body
|
| Sep 2, 2011 at 7:09 | comment | added | Gjergji Zaimi | Great, I edited the answer to reflect that. | |
| Sep 2, 2011 at 7:08 | history | edited | Gjergji Zaimi | CC BY-SA 3.0 |
added 341 characters in body
|
| Sep 2, 2011 at 5:21 | comment | added | Shir | I agree with Douglas, why isn't your "simple argument" in fact showing that, as you wrote, B(n)=2 for infinitely many n? | |
| Sep 2, 2011 at 5:11 | vote | accept | Shir | ||
| Sep 2, 2011 at 5:18 | |||||
| Sep 2, 2011 at 0:11 | comment | added | Douglas Zare | Your "simple argument" that there are no nontrivial ways to assign the signs for $n=p-1$, $p$ prime, solves the question as stated, since it shows that there is no $N$ so that there are nontrivial solutions for $n\gt N$. | |
| Sep 1, 2011 at 20:12 | comment | added | Gjergji Zaimi | When looking at the Cohen-Shpilka-Tal paper I mentioned above you will see that the relevant results in Buhrman and de Wolf hold for a slightly more general setting, and they emphasize the point that current lower bounds on the degree come from mod p considerations and no technique is known that distinguishes between a very small range and a comparably sized range. | |
| Sep 1, 2011 at 19:29 | comment | added | Shir | Thanks. A useful reference is the survey of Buhrman and de Wolf on complexity measures of boolean functions, where current results and some proofs appear. | |
| Sep 1, 2011 at 18:16 | history | answered | Gjergji Zaimi | CC BY-SA 3.0 |