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.