Grades

Hi All,
just wanted to let you know that I compiled the course grades. I will report them to the midrasha, including exercise and scribe notes grades, and they will hopefully be available for you to see in a few days (or a bit more considering the holidays).

Happy new Jewish-calendar year,

Guy

HABF - the end

I hope you enjoyed our course - I certainly did. But all good things come to an end and this course is no exception, even though there are many interesting results and topics that we haven't touched. If any of you would like to learn more, or even actually work in this area, feel free to talk to me about it.

Have a nice rest-of-your-life.

Guy

p.s.: Amir told me he is a bit behind on exercise grading, so final grades may take a while longer.

Mistake in question 5

As Zvika Brakerski pointed out to me, in the definition of Entropy (Ent) in question 5, g should be squared everywhere. That is, $\mathbf{Ent}(g)=\mathbf{E}_x[g^2(x)\ln(g^2(x)] - \mathbf{E}_x[g^2(x)] \mathbf{E}_x[\ln(g^2(x)]$. I'm writing this from a computer that doesn't support mathml fonts, so I can only hope the formula shows correctly on computers which do support it.

Mistake in question 2

In home assignment #5, there is an error in question 2. Instead of the probability that $|f(x)|>t$, the bound should be on the probability that $|f(x)|>t\cdot||f||_2$. Thanks to Ori Brostovski for pointing that out.

Bonus question

I just added a 15 points bonus question (question no. 7) to the home assignment. If you have only 6 questions in your assignment please download it again to see the bonus question.

Exercise no. 5

A shiny new home assignment is finally online. Submission is due two weeks from now on June 23rd. Enjoy!

Last class today!

Don't forget that we have class today (Wednesday) between 16:00-18:00. I didn't verify that we have the room, but we'll meet at the usual place anyway, and move somewhere else if needed.

Don't say "I didn't know".

Restating some announcements

Let me repeat two announcements, for the benefit of those abroad and all the ships at sea.

First, the deadline for submitting home assignment #4 has been postponed to the coming Monday (the 26th, and remember that class will be held in Ziskind 261). Also, two additional classes will be given after next week's one, to compensate for the classes we missed during the semester.

Change of room May 26

Next week, on May 26, class will be held in Ziskind 261 and not in the usual place.

Clarifications, thoughts, and a bonus regarding ex. 4

The telepathic capabilities of some of you are weaker than I hoped, and so I have to better clarify some of the questions from home assignment #4.

In question 1(b), you should show that for every odd $n$, the majority function over $n$ coordinates has the highest weight on the first level out of all transitive Boolean functions on $\{-1,1\}^n$ (recall that the weight of a function $f$ on the first level is $||f^{=1}||_2^2$). You are then required to compute the limit of the weight of majority on the first level where the number of coordinates tends to infinity.

In question 3, you are required to accomplish the amazing feat of testing whether three functions are correct code-words, and in addition verifying that they satisfy an elaborate constraint, by looking at three bits total. But is this really so amazing? We know how to test that a string is a Hadamard code-word by looking at three bits, and testing whether one function equals the product of the other with a given character is really easy with even two bits queries, so we could just toss some coin and use the outcome to decide to test one of the properties that the functions need to satisfy. To pass this combination-test with very high probability, the functions must indeed satisfy (or be close to satisfying) all the required properties.

So the amazing part is actually not the fact that you can test all these things by three bit queries, it is the fact that you can do this and maintain optimal soundness (namely $\frac12+\delta$) - to get that you really have to use the same three bits to test all properties at once. By the way, the fact that $\frac12$ is the 'true' soundness barrier is not obvious here, since we are not restricting ourselves to multiplicative tests, but it is known to actually be optimal.


Question 4 deals with yet another amazing feat - testing the long-code with just two queries. And if this isn't enough, in the first part of question 5 you are asked (or at least, I meant to ask) to extend the test from question 4 to one that still uses just two bit-queries, and tests two strings for both being long-code words and for satisfying a given permutation constraint. The requirement for soundness $\delta(\epsilon)$ is a mistake - it should read $1-\epsilon-\delta(\epsilon)$, same as the expression in question 4.

In section 5(b), you need to use the test from the previous section to show a hardness of approximation result. Since I didn't yet show in class how to obtain hardness results from tests, I'll consider sections 5(a) and 5(b) as two separate questions. Moreover, you may defer submitting the answer to question 5(b) to the next exercise. However, if you choose to take a stab at it and submit it with the current exercise, you'll get a 10 point bonus if you solve the section correctly.

correction for ex. 4 q. 1

A small correction for the first question in assignment #4: in section (b) you are required to show that Majority has the highest first level weight out of all *transitive* Boolean functions. Also, although I forgot to mention this in the exercise, you should also compute that weight.

Homework #4

Once again, a new homework assignment has been put on the course homepage. It's due on the 19th, but I think it would be beneficial if you at least look at it before the next class (at least it would enable you to try to squeeze some hints out of me on Monday..). Note that question #5 has some notions that we are only going to define on Monday though.

Decoding schemes

For applications of hardness of approximation we often need a 'decoding scheme' - for a fixed code $C$ and a given word $f$, the scheme should return some possibly random codeword $f'$ which in some sense is a decoding of $f$. The codewords $f'$ that are returned may sometimes be totally uncorrelated with $f$, and yet in some sense they are still a reasonable decodings of $f$: an example may be the case where $C$ is the long-code, $f$ is a character $f=\chi_{\{7,69\}}$, and the decoding scheme returns either $f'=\chi_{7}$ or $f'=\chi_{69}$. These are reasonable decodings of $f$, and yet their correlation with $f$ is zero.

The problem is now how to define this 'reasonable decoding scheme'. Since I failed to give a full definition in class of a reasonable decoding scheme in the case of constraint testers, let me try to compensate by giving the definition here, together with some additional explanations. I will still repeat some of the last part of today's class next week.

Let up start with the definition of a decoding scheme.

A decoding scheme for a code $C$ is a mapping $D$ that associates each string $f$ with a distribution $D(f)$ over codewords from $C$ and possibly the bottom symbol $\bot$ (the bottom symbol will basically appear when the decoding scheme gives up).

Note that in the above definition we gave the decoding scheme total freedom - it can always return just one codeword, it can return the uniform distribution over all codewords, or it can just give up and always return bottom. There are definitely many lousy decoding schemes, but in the definition of a test we'll require good ones.

We decide if a decoding scheme is good by whether the decoding it returns satisfies the constraints that we want to verify, but as noted in class someone can just try to sell us a couple of decoding schemes that always return the same strings $f',g'$, which happen to satisfy the given constraint, and have nothing to do with the original $f$ and $g$. Indeed, to make the decoding problem interesting we need to look not only on one constraint, but on a family of constraints: the decoding scheme will have to figure out $f'$ and $g'$ (given $f$ and $g$ respectively) without knowing which constraint from the family is tested.

A constraint family over codes $C_1,C_2$ is a set $\{R_\lambda\}_{\lambda\in \Lambda}$ of relations $R_\lambda$ on $C_1$ and $C_2$. Given $f\in C_1$ and $g\in C_2$, we say that they satisfy the $\lambda$-constraint in the family if $fR_\lambda g$.

We are going to look at tests over families of constraints. The testing procedure will be given an index $\lambda$ of a relation in the family, and then query some bits from the given strings $f$ and $g$. Formally,

A $q$-query constraint tester for codes $C_1,C_2$ and a family $\{R_\lambda\}_{\lambda\in \Lambda}$, is a procedure that given two strings $f,g$ and an index $\lambda$, makes $q$ queries to $f$ and $g$ and then either accepts or rejects.

We say that the tester has completeness $c$ if when $f\in C_1$, $g\in C_2$ and $fR_\lambda g$, the test accepts with probability at least $c$. The more difficult part is to define soundness. We say that a tester has soundness $s=s(\delta)$ for $\delta$-satisfaction if there are decoding schemes $D_1$ for $C_1$ and $D_2$ for $C_2$ such that the following holds: for any strings $f,g$ and any index $\lambda$, if
$\Pr[$tester accepts on $f,g,\lambda]>s$,
implies
$\Pr_{f'\sim D_1(f), g'\sim D_2(g)}[f'R_\lambda g']\geq \delta$.

As food for thought, consider the problem of testing whether $f$ and $g$ are in the Hadamard code and that additionally $f=\chi_T g$ for a given $T$. Can you devise a three query constraint tester for this problem? Can you show some non-trivial bounds on its soundness?

Happy vacation

I wish you all a happy vacation - and to keep your brain from clogging on matzo's, don't forget to work on the home assignment.

On a slightly different note, a few of you are extremely late on handing exercises and this prevents me from talking about the solutions, which in turns hurts everyone else. If you are late on any of the submissions, you can submit without penalty until the class on Monday, April 28th. Any late submission past that date without my approval will not be accepted. There will be no postponements from now on without my explicit consent.

Another home assignment

I am happy to announce that homework assignment no. 3 now proudly inhabits the course homepage. Due date is April 28, but you'd be doing yourselves a favor if you look at it much sooner, before you forget all the proof techniques from recent classes.

Shock and awe

I'm not really sure about awe, but I sensed a bit of shock in Monday's class. I guess the fact that this was the first class in three weeks, plus the late time, plus my jetlag, plus the fact that the proof I showed was quite complicated all took their toll.

Not being able to follow everything in class is actually not such a bad thing - it is often unavoidable when learning serious math. But to really gain something from a class were you didn't follow everything, or just barely did so, it is essential to go over the material again and make sure that you eventually understand it. There will be no written assignment this week - your assignment is to go over Monday's class and to really understand all the details and ideas. If you have questions, feel free to ask me.

To help you out a bit, let me try to have another short attempt at explaining the crux of the proof, which is the lemma saying that if $g=c+\sum a_ix_i$ and $\alpha=\sum a_i^2$ is 'small enough', then $||g-\sign(g)||_2^2\geq \alpha(1+o_\alpha(1))$. First, if $c$ is close to zero this is easy - but you should verify that you know why. If $c$ is closer to, say, $1$ than it is to zero, the point is that $g$ will almost always be positive (but it can also be negative sometimes, even if $\sum a_i^2$ is small - can you see why?). That's why the variance of $g$ will be very close to the variance of $|g|$, which is good because
(a) we know the variance of $g$ - it equals $\alpha$, and
(b) The term $||g-\sign(g)||_2^2$ can be bounded from below by the variance of $|g|$.

All that is left is therefore to bound the difference between the variance of $g$ and that of $|g|$, which we managed to show (modulo the claim that $c+\mathbb{E}[|g|]\leq 4$) is bounded by the expectation of the negative part of $g$. Again, this seems easy since we can use Chernoff to show that the probability that $g$ is negative is very small - the $x_i$'s with their smallish coefficients must win the battle against the big $c$ for this to happen. The problem is that we need a bound not on the probability that $g$ is negative but on the expectation of its negative part. We therefore use a formula that writes the expectation of a random variable in terms of the probabilities of it being large, namely $\mathbb{E}[X]=\int_{t=0}^\infty\Pr[X>t] dx$. That's how we use the Chernoff bound to estimate an expectation rather than a probability - this is actually a standard and important trick. Once we write down the integral, it's all over but the shouting.

Exercises

Before giving some comments about the first exercise, here are some general comments about submitting exercises (the comments are sorted by some order): Read the exercise at least once before you submit it. Check that what is written is what you intended to write. Check that it is also correct. If you use some claim, state it exactly, and give some reference to it (e.g., proved in class). If the question has several parts, try to understand how do the parts combine. See if you can make the argument simpler (perhaps using ideas discussed in class). Try to understand the purpose of the question (or the person who gave the question).

Going back to the first exercise, here are comments about the solutions you submitted
(comment 1. corresponds to question 1., for example).

1. To calculate a limit, one needs to show that the limit actually exists, and so one needs to consider every n (not just even n's, for example).
2. This question is all about doing some exact calculation. So writing ~ without explaining what do they mean, and using non-integer m(t) are missing answers.
3. This question has the largest amount of solutions: some of the answers are short and precise, some of the answers are correct and long, and some of the answers can actually be made into correct argumets, but lack the needed definitions and/or details.
4. (a) There is a subtle issue, which some of you addressed, that the statement holds with probability 1 (and not for every value that variables might take). (b) After the comments above, some of you did not use (a) - this was needed.

Regarding the grades for the exercises, we decided to give a grade from 0 to 10 for each question. The final grade will somehow depend on these numbers.

No class on Monday

No class will be held next Monday (March 24th), again, since I'll be abroad. This will be as hard for me as it is for you, but at least you have the exercise to keep you company. We'll meet again on March 31st.

See you soon,

g

First exercise - Last call

If you have not submitted the first exercise yet but you wish to do so, please contact Amir as soon as possible. The first window will be closed soon.

Some comments about homework #2

Here are some comments about the questions in the second home-assignment, which I hope you may find interesting. They are listed by question numbers. Enjoy!

1. For a fixed function $f$, the way the $p$ norm of $f$ behaves as a function of $p$ can say a lot about the structure of $f$, as we shall see in the future. In this question we observe a very simple yet useful behavior of the $p$ norm which holds for all functions, namely that it (weakly) increases with $p$ and tends to the $\infty$ norm as $p$ goes to $\infty$. Unlike the triangle inequality for the $p$ norm, which is quite difficult, the monotonicity of the norm has a short and simple proof.
   
   
2. We said in class that the majority function has the highest weight on linear characters out of all 'non-junta-like' Boolean functions. The technique for proving that will come more naturally in the next few weeks, so this question discusses two other interesting extremal properties of the majority function: out of all Boolean valued monotone functions, majority has the highest possible total influence (would you believe that you could prove such results using the very basic techniques that we covered so far? Would you be able to prove this without learning Fourier techniques first?). Also, majority has the largest possible sum of linear coefficients out of all Boolean functions, monotone or not. If you want a slightly higher challenge, prove that majority also has the largest possible sum of absolute values of linear coefficients out of all Boolean valued functions.
   
   
3. In this question you are asked to find a formula for the variation, defined in the previous home assignment, in the Fourier phase (namely, in terms of Fourier coefficients) - this may require some thought. But once you have the formula, note that showing the sub-additivity of the variation, which you were required to do in the previous assignment, now becomes trivial. The other two important properties of the variation, which are stated in sections (b) and (c), also follow easily from the formula. These properties show that the variation of a function $f$ on a set of $T$ coordinates exactly captures how well $f$ can be approximated by a function which is independent of $T$. This means that the variation (and the influence as a special case) really measures in a quantitative way how much a function depends on a set of coordinates.
   
   
4. It is intuitively obvious that a balanced function that depends equally on all of its coordinates cannot be approximated by a junta, a function that only looks at a few coordinates (the requirement for balancedness comes since otherwise the function may be constant, which is not really fair). Here you are required to prove this fact for a symmetric function. Proving this for a transitive function turns out to be more challenging, and if you do you'll get extra credit (say, 15 points).
   
   
5. We already know that the set of characters is exactly the set of multiplicative functions. Also, note that a function $f$ is multiplicative if and only if $f(x)f(y)f(xy)=1$ for all $x$ and $y$, or alternatively, if and only if $\mathbb{E}[f(x)f(y)f(xy)]=1$. But once you write the expectation in terms of the Fourier coefficients of $f$, it becomes relatively easy to show a robust version of the above observation, namely that a Boolean function which is 'mostly' multiplicative must 'almost' be a character. This is a very strong fact, because it enables us to check whether a function is close to a character by just picking a few triples $(x,y,xy)$ and only reading the value of $f$ on these triples. This question may require a bit more steps of derivation than others (but as I hear from Amir, it may need less than many of you actually often use..).
   

Homework #2

A new homework assignment has just been published on the course web site. Submission deadline is March 31st but I urge you to take a look at it soon and think about it, even if you are not taking the course for credit. If you find some of the questions difficult, thinking about them in the background for a while may help you soften them a bit before you take another bite.

Scribes

Here is the current list of talk-scriber, where each scriber is numbered according to the talk he or she is supposed to write scribe notes for. To make changes or to commit to additional talks please contact Amir.

1. Gilat Kol.


2. Or Meir.


3. Noam Arkind.


4. Ofira Burstein.


5. Igor Shinkar.


6. Sergei Novikov.


7. Zvika Brakerski.


8. Shira Kritchman.


9. Chandan Dubey.


10. Dmitry Frumkin.


11. Shlomo Joseph.


12. Eric Shelef.


13. Ori Brostovski.
14. Inbal Talgam.

Theory day

On March 17th the open university is having a theory day. Since I guess many will want to attend, including myself, class will be canceled. There is a good chance that either the class on March 24 or the one on March 31st will also be canceled due to some traveling on my part.

I would like to compensate for the lost time by giving at least one out-of-schedule class sometime next week. Please think about what would make an appropriate time, and either make suggestions in the comments or when we meet on Monday.

And speaking of the theory day, the following video will probably not be discussed there.

How to scribe

Here's some information about writing scribe notes for the course - I hope you find it helpful. Feel free to use the comment section below for any appropriate purpose.


1. Take notes

To write scribe notes for a class, the first thing you need is to know what was taught in it. Not all things are written on the board, so for good scribe notes it is essential to have notes of all things said in class, including questions asked and answers given (bad jokes and petty mistakes can be left out). Borrowing other peoples' notes in addition to yours may be helpful and is recommended. Using notes from other courses that you find online or any other source is also fine, just as long as what you eventually write are scribe notes for the class that was actually taught.

2. Understand

There are several purposes for lecture scribe notes writing. One is that to write good class notes, one should get a full and deep understanding of the material covered in that particular class. Since we are all busy people with finite resources and energy, most of us tend to get sloppy and not take the time to get to the bottom of things we are taught. It is good for us to be forced, once in a while, to think deeply at least about a specific subject and to understand it well enough so that we can present it and explain it to others.

Before you write scribe notes, you should understand the class as well as you can. Not just how proofs go, but what is the motivation for studying them in the first place, why they work, what the central ideas and tricks are, what difficulties are overcome etc.. Don't hesitate to consult me about issues you have with the material - I would be glad to discuss it with you or help with any difficulties.

BTW, as the course progresses understanding classes will require more background knowledge from previous classes, so securing an earlier class to write scribe notes for may make your life a bit easier.

3. Explain

A scribe note is not a simple transcription of what went on in a particular class. Sometimes the best way to write one is to just linearly go over whatever was going on in class, even mentioning questions that were asked and answers that were given. Other times such a linear description would be incomprehensible and a different approach should be taken. Thinking about how to best present the material is an important part of writing scribe notes. When you write scribe notes well, people around the world who you never met may use it for their scientific needs - isn't this great?

Good scribe notes should explain the material taught in class in a way that is useful to someone that did not attend it. It should explain not only the definitions claims and theorems, but also the motivations, intuitions, and emphasis. Sometimes good scribe notes must contain information that wasn't even covered in class, such as computations that were not done fully or in an exact manner. Ask yourself the ultimate question - will someone reading my scribe notes get a clear picture of the material that was covered?

2. LaTex

Scribe notes should be written in LaTex - it is a world standard for writing documents that are nicely formatted and contain both math and text, and if you don't know how to use it then this is your chance to learn. A source LaTex file is a text file that can be easily read by the naked eye, and when compiled it can generate very nice looking ps or pdf files.

You can find plenty of information about LaTex and its uses on the web, but the easiest way to learn it is to take a LaTex file that was already prepared and change it to your needs. There are template files on the course web page for writing scribe notes - use them. If you don't know how to replicate a formula or a notation shown in class, make sure to find out how to properly do it - find it on the web, in other peoples' notes, or ask me. But don't just change notation or use weird formulations just because you can't figure out how to do it right in LaTex. In LaTex, there's always a way.


4. Show me the notes

This is not mandatory, but if you want to do a good job (and get a good grade) I advise you to show me your scribe before you submit it - I may have remarks that will help you improve it. It wouldn't hurt to also show it to whoever else is willing to take a look. Scientific text is extremely difficult to write well, and nearly all texts can be helped by outside comments.

5. Submit

I don't want to put too much pressure on you, but I wouldn't want to keep getting scribe notes for classes after I forgot all about them. So l guess a one month limit on scribe submission is reasonable. Submit the scribes to me, by email, and include both a PDF file and all LaTex source files that you used (even if these are files that you took from the course web site). I will put all these files online, unless you ask me otherwise.

The first mistake announcement

I hope there won't be many of these posts, but some are unavoidable in a course that goes where no course has gone before. So let's get to it: in class we proved that if $f(X_1,X_2)$ is a function of two independent random variables then
$\mathbb{V}_{X_2}[\mathbb{E}_{X_1}f(X_1,X_2)]\leq \mathbb{E}_{X_1}[\mathbb {V}_{X_2}f(X_1,X_2)]$. We gave a condition for when equality holds above, which was wrong. Finding what is the correct necessary and sufficient condition appears as a question in the first home assignment.

Blog math

The story of including math formulae in web pages and blogs in particular is long and sad. The best I could do to solve the problem here is use some script that translates latex to mathml, which is a standard for math on the web. One catch with this approach is that firefox often needs new fonts to be installed for this to work well, and explorer may need a special plugin (I don't know the situation with other browsers).

If the formula

and the formula
$\displaystyle{Y=\sqrt{\frac{X^2+1}{2\cdot\frac1{1+\beta}}}}$
don't look kinda the same to you, your browser may need some assistance.

For firefox help try here, and for explorer this plugin should do the trick.

New home assignment

Hi Everyone, I got some great news for you - the first homework is out and is available from the course homepage. Submission is due on Monday, March 10th - please submit directly to Amir.

Even if you do not need credit for the course, I advise you to at least take a look at this and other homework assignments - they will often cover interesting or delicate points that I didn't have time to go over in class. Have fun, and add comments on this post if you have questions, problems or protests.

123 testing

Hi Everyone,
this is the blog where I will announce exercises, procedural details, and embarrassing mistakes for the course "Harmonic Analysis of Boolean Functions and Application to Computer Science". The Course will be given in the autumn of 2008. Participants of the course should subscribe to the blog. If you, like me, are not familiar with RSS, the easiest thing would be to use the link on the right of this page and subscribe to get the new posts of this blog by email.

Hope you enjoy the course.

g

P.S.: If you feel like leaving comments on any of the posts, please do. I'll try to reply when appropriate.