Well, the course is over -- thanks to everyone for coming and making it a fun affair; I really appreciate it. Don't forget to fill in the course evaluation forms.
Have a good summer.
Friday, May 04, 2007
Thursday, May 03, 2007
Open Problems
The final set of lecture notes are posted -- they contain open problems. Some are definitely harder than others; some are definitely more interesting than others. If you have any more questions about them, feel free to comment. Also, if you are interested in working on any of them, let me know! If you are looking for an easyish-to-think-about problem, one that you can think about idly with a pen and paper while riding the bus, I might suggest the problem of extending the decision tree/influences inequality to real-valued functions.
I probably missed half a dozen better open problems out there. I may add to this list as they occur to me. To paraphrase Mitch Hedberg, these are the open problems I could think of today.
I probably missed half a dozen better open problems out there. I may add to this list as they occur to me. To paraphrase Mitch Hedberg, these are the open problems I could think of today.
Homework #5 graded
Homework 5 is graded. The average was 90%, with two people getting 39/40.
Most problems were done pretty well; interestingly, only one person attempted #7, even though it has the shortest solution after #3. A number of people did #2 but no one really got part (b) exactly correctly. The issue there is that you have a real-valued (not integer-valued) random variable and you know that it has exponentially small tails; you want to show that the contribution to its $L_1$-norm from large numbers is exponentially small. There is a battle here, between, the contribution of $|u|$ and the probability $O(e^{-u^2/2})$, which of course the exponentially small quantity is going to win; still, one has to integrate, as shown in the solutions.
Also, nobody got #6(c) quite correct. The Tribes function is not exactly balanced; its empty Fourier coefficient is just known to be $\pm O(\log n / n)$. Thus $\mathbb{N}\mathbb{S}_{1/2 - \gamma}(T)$ will always be at most $1/2 - \Omega(\log^2 n / n^2)$, which is why the condition $\gamma \geq 1/n$ is necessary.
I'm also pleased to report that the overall homework average was 83%. Good job, y'all.
Most problems were done pretty well; interestingly, only one person attempted #7, even though it has the shortest solution after #3. A number of people did #2 but no one really got part (b) exactly correctly. The issue there is that you have a real-valued (not integer-valued) random variable and you know that it has exponentially small tails; you want to show that the contribution to its $L_1$-norm from large numbers is exponentially small. There is a battle here, between, the contribution of $|u|$ and the probability $O(e^{-u^2/2})$, which of course the exponentially small quantity is going to win; still, one has to integrate, as shown in the solutions.
Also, nobody got #6(c) quite correct. The Tribes function is not exactly balanced; its empty Fourier coefficient is just known to be $\pm O(\log n / n)$. Thus $\mathbb{N}\mathbb{S}_{1/2 - \gamma}(T)$ will always be at most $1/2 - \Omega(\log^2 n / n^2)$, which is why the condition $\gamma \geq 1/n$ is necessary.
I'm also pleased to report that the overall homework average was 83%. Good job, y'all.
Tuesday, May 01, 2007
Szemeredi's Regularity Lemma, full version
The lecture notes for today are up; they include a full proof of the Szemeredi Regularity Lemma for $\mathbb{F}_2^n$ and also the associated result about testing "triangle"-freeness of subsets of $\mathbb{F}_2^n$.
Subscribe to:
Posts (Atom)