tag:blogger.com,1999:blog-36763731.post7315879126636238454..comments2016-11-14T23:53:43.172-05:00Comments on 18-859S: Analysis of Boolean Functions: Homework 3Ryan O'Donnellhttp://www.blogger.com/profile/01760886084136827344noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-36763731.post-20616276169705817192008-04-29T08:23:00.000-04:002008-04-29T08:23:00.000-04:00You should shift this to wordpress. It has better ...You should shift this to wordpress. It has better latex supportThe Quarkhttps://www.blogger.com/profile/00790797402763498609noreply@blogger.comtag:blogger.com,1999:blog-36763731.post-45142860867504533442007-03-05T20:06:00.000-05:002007-03-05T20:06:00.000-05:00Anon: You don't have to learn anything in 3b.Anon: You don't have to learn anything in 3b.Ryanhttps://www.blogger.com/profile/17737696490831554328noreply@blogger.comtag:blogger.com,1999:blog-36763731.post-1164829728016889492007-03-05T13:52:00.000-05:002007-03-05T13:52:00.000-05:00A question about 3b:Are we supposed to get weak le...A question about 3b:<BR/><BR/>Are we supposed to get weak learning under the uniform distribution, or under any distribution?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-36763731.post-50115763722883765302007-03-05T10:27:00.000-05:002007-03-05T10:27:00.000-05:00Hi Aaron.Re 6a: Either is fine; with the question ...Hi Aaron.<BR/><BR/>Re 6a: Either is fine; with the question as stated, the algorithm can always choose eps to be poly(eps/n^d) if it wants to use this for learning.<BR/><BR/>Re 4a: You're right, this is a mistake. <B>The algorithm should also get query access.</B> I have corrected this in the online version of the homework.Ryanhttps://www.blogger.com/profile/17737696490831554328noreply@blogger.comtag:blogger.com,1999:blog-36763731.post-25260361035867166842007-03-04T16:01:00.000-05:002007-03-04T16:01:00.000-05:00Another question, this time about 4a:What is meant...Another question, this time about 4a:<BR/><BR/>What is meant by access to -random- examples from f? Do we also have query access to f? Can we evaluate f on elements from the epsilon-biased set?<BR/><BR/>AaronAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-36763731.post-39942217226357771262007-03-03T23:56:00.000-05:002007-03-03T23:56:00.000-05:00A question about problem 6a:Do we really want to s...A question about problem 6a:<BR/><BR/>Do we really want to show that with probability 1-delta the empirical estimate of every fourier coefficient is within epsilon of the true coefficient, and not instead, show that the sum of the squares of the differences is at most epsilon (That the empirical function is epsilon close). It seems like we need epsilon-closeness for learning, unless the epsilon in this problem is not the same epsilon from the low degree algorithm.<BR/><BR/>AaronAnonymousnoreply@blogger.com