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.