Timeline for Robustness of splitting a junta

Current License: CC BY-SA 3.0

13 events

when toggle format	what		by	license	comment
Nov 19, 2012 at 16:06	history	edited	Neal Young	CC BY-SA 3.0	typos
Nov 18, 2012 at 22:36	history	edited	Neal Young	CC BY-SA 3.0	reorganized to fit rewording of the original question
Nov 18, 2012 at 17:20	comment	added	user887		Sincere thanks Neal! This line of reasoning is quite enlightening.
Nov 18, 2012 at 17:18	vote	accept	CommunityBot		moved from User.Id=887 by developer User.Id=4352
Nov 18, 2012 at 17:18
Nov 18, 2012 at 16:39	history	edited	Neal Young	CC BY-SA 3.0	added 98 characters in body
Nov 18, 2012 at 16:15	history	edited	Neal Young	CC BY-SA 3.0	added 4 characters in body
Nov 18, 2012 at 16:09	comment	added	Neal Young		I've edited it to add the extension to general k. And Yuri's argument below gives a slightly looser factor with an elegant probabilistic argument.
Nov 18, 2012 at 16:08	history	edited	Neal Young	CC BY-SA 3.0	added 1764 characters in body
Nov 18, 2012 at 13:30	comment	added	user887		First of all, thanks Neal! This indeed sums it up for $k=0$, and sheds some light on the general problem. However in the case of $k=0$ the problem is a bit degenerate (as $2k=k$), so I'm more curious regarding the case of $k \ge 1$. I didn't manage to extend this claim for $k>0$, so if you have an idea on how to do it - I'd appreciate it. If it simplifies the problem, then the exact constants are not crucial; that is, $\epsilon/2$-far can be replaced by $\epsilon/c$-far, for some universal constant $c$.
Nov 18, 2012 at 3:35	history	edited	Neal Young	CC BY-SA 3.0	added Lemma 2
Nov 18, 2012 at 0:48	history	edited	Neal Young	CC BY-SA 3.0	added 172 characters in body
Nov 18, 2012 at 0:37	history	edited	Neal Young	CC BY-SA 3.0	added 3 characters in body
Nov 18, 2012 at 0:31	history	answered	Neal Young	CC BY-SA 3.0