HW3 extension | |
|
Dear students, To allow for you to make the most of office hours this Tuesday, HW3's deadline has been postponed to Thursday. Best, David |
| עדכון אחרון ב-2/2/2025, 16:26:36 Last updated on 2/2/2025, 16:26:36 Последняя модификация2/2/2025, 16:26:36 تمت الحتلنة الأخيرة ب-2/2/2025, 16:26:36 |
Office Hour Change | |
|
Dear students, This week's office hour will take place immediately after class, i.e., at 12:30. Best, David |
| פורסם ב-2/2/2025, 15:26:22 Created on 2/2/2025, 15:26:22 Создано2/2/2025, 15:26:22 تم النشر ب-2/2/2025, 15:26:22 |
HW3 FAQ | |
|
Dear students, I created an FAQ section for HW3. Do email if you have more questions not covered by the FAQ. (New baby is causing sleep deprivation, but I should find time from now to answer questions as they come in :-)) Please download the assignment, where two typos were fixed (thanks Matan and Liam!): - In 3.3(c) the target runtime is O(m^{3/2}), and not O(m^3) as was written before, - In 3.4, in an MIS, for each vertex v, either it is is in the MIS or *some* (not *all) of its neighbors are in the MIS. Cheers, David |
| עדכון אחרון ב-31/1/2025, 14:50:57 Last updated on 31/1/2025, 14:50:57 Последняя модификация31/1/2025, 14:50:57 تمت الحتلنة الأخيرة ب-31/1/2025, 14:50:57 |
Class and Office Hours Canceled Today | |
|
Dear students, Class and office hours are canceled today. See previous announcement for the reason :-) For questions about HW3, feel free to email me, though I may take a while to answer. If you're stuck on one part, continue to the next ones. See Note 1 in the homework sheet. The last lecture of the course will take place next week. Wish us luck! Best, David |
| פורסם ב-28/1/2025, 08:02:33 Created on 28/1/2025, 08:02:33 Создано28/1/2025, 08:02:33 تم النشر ب-28/1/2025, 08:02:33 |
Some Announcements | |
|
Dear students, The next lesson, whether it be this week or next week, will be the last one for the semester. (Those of you who have seen how pregnant my wife is can guess why :-) ) Currently the plan is to have a lesson this week and cancel next week's lesson, but things may change, in which case I will announce this. Before the next lesson, I strongly recommend you revisit last week's lesson, particularly the fractional matching algorithm in Section 10.1.3. Finally, the talk in the theory lunch by Or Zamir on the streaming lower bound breakthrough will take place this Wednesday, in Taub 4, at 13:00. Food (sushi) will be available there stating at 12:45. You are all welcome to come. Generally, the theory lunch may be of interest to you going forward. See https://theory.cs.technion.ac.il/seminar/future/ for upcoming talks and link to join the mailing list. Best, and see you in class, David |
| עדכון אחרון ב-26/1/2025, 15:16:21 Last updated on 26/1/2025, 15:16:21 Последняя модификация26/1/2025, 15:16:21 تمت الحتلنة الأخيرة ب-26/1/2025, 15:16:21 |
HW2 final extension | |
|
Dear students, Some students asked for a further extension for HW2. The HW deadline has accordingly been postponed to Thursday, January 23rd. As other students pointed out, the recently uploaded Lecture 7 mistakenly didn't contain the update. See the updated lecture notes, with the only changes being the blue text in Theorems 7.12+7.13. Hopefully this should help if you're stuck on part of HW2. Best, David |
| עדכון אחרון ב-21/1/2025, 14:21:09 Last updated on 21/1/2025, 14:21:09 Последняя модификация21/1/2025, 14:21:09 تمت الحتلنة الأخيرة ب-21/1/2025, 14:21:09 |
HW3 (focused on MPC) is out | |
|
Dear students, HW3 can be found under the HW tab. It focuses on MPC algorithms, as in the previous and next few lectures. Due date is February 4. Enjoy, David |
| עדכון אחרון ב-20/1/2025, 16:16:42 Last updated on 20/1/2025, 16:16:42 Последняя модификация20/1/2025, 16:16:42 تمت الحتلنة الأخيرة ب-20/1/2025, 16:16:42 |
Lecture 7 correction | |
|
Dear students, In Lecture 7, as pointed out by Tal (thanks!), in Theorems 7.12 and 7.13, the JL matrices (which become subspace embeddings) are applied to n-dimensional vectors, and not d-dimensional ones, so these matrices' dimensions are k x n, and not k x d. The lecture notes were corrected accordingly. Best, David |
| עדכון אחרון ב-19/1/2025, 09:39:26 Last updated on 19/1/2025, 09:39:26 Последняя модификация19/1/2025, 09:39:26 تمت الحتلنة الأخيرة ب-19/1/2025, 09:39:26 |
HW2 3(d) | |
|
Dear Students, In question 3, part d, there was a factor of roughtly n^rho missing when considering the contribution of the document lengths to the running time, and some polylogs too. (Thanks Liam for pointing this out!) The required running time guarantees were increased appropriately. See the updated HW2 PDF. To make things easier, in this part you can feel free to only get the running time in expectation (though you have the tools to convert these to worst-case bounds). Best, David |
| עדכון אחרון ב-18/1/2025, 15:55:23 Last updated on 18/1/2025, 15:55:23 Последняя модификация18/1/2025, 15:55:23 تمت الحتلنة الأخيرة ب-18/1/2025, 15:55:23 |
HW2 Clarification | |
|
Dear students, In HW2, 2(d): you should upper bound the probability that the maximum *absolute value* of a coordinate of z is large (thank Benny!). Assuming you follow the preceding hint, your proofs should already be proving this, rather than an upper bound on the (non absolute) value of z_i. Moreover, in 2(d) and 2(e) since the objective is an asymptotic bound, feel free to prove the results with the constant sqrt(2) replaced by some larger constant. Best, David |
| עדכון אחרון ב-17/1/2025, 16:53:47 Last updated on 17/1/2025, 16:53:47 Последняя модификация17/1/2025, 16:53:47 تمت الحتلنة الأخيرة ب-17/1/2025, 16:53:47 |
HW2 Deadline Extended by One Day | |
|
Dear Students, HW2's deadline has been extended. Its new due date is next Tuesday, January 21, 19:00. Cheers, David |
| עדכון אחרון ב-14/1/2025, 17:01:51 Last updated on 14/1/2025, 17:01:51 Последняя модификация14/1/2025, 17:01:51 تمت الحتلنة الأخيرة ب-14/1/2025, 17:01:51 |
Typos + fixes to HW2 and Lecture 8 | |
|
Dear Students, Following a number of questions by students in class and during office hours (thanks!), some typos and other fixes were made to HW2 (in red). Similarly, in Lecture 8 (LSH), in Corollary 8.5, the lemma holds for p2 < p1, and not the other way round, as was previously stated. Cheers, David Bonus: As a further motivation for LSH and searching for near-duplicates among data points before training ML models off of them: 1. Prompt ChatGPT to show you a clock showing 19:35 (or pretty much any time other than 10:10). Did you get the right answer? Did you get 10:10? 2. Now Google "clock". How many of the results (even accounting for Google trying to output diverse results) show a clock showing 10:10? Can you relate these two steps? |
| פורסם ב-14/1/2025, 16:10:08 Created on 14/1/2025, 16:10:08 Создано14/1/2025, 16:10:08 تم النشر ب-14/1/2025, 16:10:08 |
Classroom change to Taub 2 | |
|
Dear Students, As with the last lesson, to move further away from the construction noise, lectures will move from Taub 3 to Taub 2 until the end of the semester. See you there. Best, David |
| עדכון אחרון ב-13/1/2025, 13:39:59 Last updated on 13/1/2025, 13:39:59 Последняя модификация13/1/2025, 13:39:59 تمت الحتلنة الأخيرة ب-13/1/2025, 13:39:59 |
HW1 graded and returned | |
|
Good morning, HW1 has been graded and feedback has been returned. Please read the grader's feedback carefully. It should help you in the following HWs (and the exam, and in general). Best, David |
| עדכון אחרון ב-12/1/2025, 07:59:40 Last updated on 12/1/2025, 07:59:40 Последняя модификация12/1/2025, 07:59:40 تمت الحتلنة الأخيرة ب-12/1/2025, 07:59:40 |
HW2 out | |
|
Dear students, HW2 is now out. Due date is January 20. Enjoy! Happy holidays, David |
| עדכון אחרון ב-25/12/2024, 18:12:19 Last updated on 25/12/2024, 18:12:19 Последняя модификация25/12/2024, 18:12:19 تمت الحتلنة الأخيرة ب-25/12/2024, 18:12:19 |
Lecture 7 notes + reminder of no class next week | |
|
Dear students, Thank you for yet another lively discussion today. The lecture notes were updated based on the discussion. As usual, if something was not clear, please reach out. Next lecture (in two weeks, after the holidays) we will move on to a less linear-algebraic topic: locality sensitive hashing (LSH). Cheers, David |
| עדכון אחרון ב-24/12/2024, 16:18:10 Last updated on 24/12/2024, 16:18:10 Последняя модификация24/12/2024, 16:18:10 تمت الحتلنة الأخيرة ب-24/12/2024, 16:18:10 |
Extension for HW1 | |
|
Dear students, To allow students time to attend another office hour before submitting HW1, the homework's due date has been postponed to Wednesday, December 25. Good luck, David |
| פורסם ב-23/12/2024, 09:08:04 Created on 23/12/2024, 09:08:04 Создано23/12/2024, 09:08:04 تم النشر ب-23/12/2024, 09:08:04 |
HW1 update + theory seminar pointer | |
|
Dear students, Following clarifying questions (thanks Liam and Yuval!): in HW1 1.5(b)+(c): prove the lower bounds for p,k≠1. See updated HW1. On another topic: as mentioned in Lecture 4, we have a weekly seminar in theoretical computer science in the department, which is a good place to: (1) get exposed to recent results and active research areas in theory, (2) meet people (students, postdocs, faculty) working in / interested in theory, (3) get free lunch :-) The seminars take place Wednesdays, 13:00-14:00, in Taub 4. See the schedule and mailing list subscription pointer here: https://theory.cs.technion.ac.il/seminar/future/ I am bringing this up because in two weeks Or Zamir is scheduled to give a talk about tight streaming lower bounds for f_k estimation, which you should be able to appreciate given your exposure to the topic in this course. Cheers, David |
| עדכון אחרון ב-17/12/2024, 14:55:31 Last updated on 17/12/2024, 14:55:31 Последняя модификация17/12/2024, 14:55:31 تمت الحتلنة الأخيرة ب-17/12/2024, 14:55:31 |
Updated Lecture 5 Notes + clarification for HW1 | |
|
Dear Students, Thanks again for an interactive lecture. Following the lecture, please find the updated lecture notes for lecture 5. Changes compared to the notes from before the lecture include: 1. A few more takeaways highlighted (JL Lemma, Chernoff Bounds + a template for proving these, and the probabilistic method). 2. Remark 5.6 added to motivate why we cared about the expected distance, or revisiting our analysis of the expectation of the Tug-of-War sketch. 3. The exact Chernoff bound for our distributions of interest were added. As mentioned in class, the variables we should have focused on were based on M rather than its scaled version A. (Or at least should have factored in the difference between them). This adds a k term in the exponent of the denominator in the Chernoff bound in Equation 5.2, which we needed later.. The notes also include the Chernoff bound for the lower tail, which is mostly the same analysis, only starting with a negative t<0. If you're less familiar with Chernoff bounds, please take a look. Following questions about HW1 by a few students: here are a few clarifications / typo fixes (thanks Benny, Tal, and Yuval!): In Question 1.1(c): you should upper bound the number of changes to the sample *in expectation* (and not in the worst case, which is clearly false). In Question 1.3(d): you should show that Y_k/k (and not Y_k) is an (eps/4,delta)-approximation of 1/(n+1). Corrections have been marked in blue in the updated HW sheet, under the HW tab. Cheers, David |
| עדכון אחרון ב-10/12/2024, 14:13:40 Last updated on 10/12/2024, 14:13:40 Последняя модификация10/12/2024, 14:13:40 تمت الحتلنة الأخيرة ب-10/12/2024, 14:13:40 |
Updated Lecture 4 Notes | |
|
Dear all, The lecture notes for lecture 4 have been updated to reflect: (1) Our discussion on the communication complexity of equality. See the appendix.* (2) A proof sketch of the coding theoretic lemma we used without proof. See the second appendix. (3) A corrected statement of Theorem 4.11: for any f_k estimation there is some relative error c=c(k) that is impossible without using logarithmic space (though for some, 1/10 relative error is achievable). (4) See also the proof of the eps^(-2) lower bound for f_0 estimation. * For those of you wondering how private coin help solve equality, I'll mention that some ideas we saw in class allow to solve equality with private randomness. You are welcome to think of this for yourself, and/or check out the appendix for a proof. Cheers, David |
| עדכון אחרון ב-8/12/2024, 17:01:34 Last updated on 8/12/2024, 17:01:34 Последняя модификация8/12/2024, 17:01:34 تمت الحتلنة الأخيرة ب-8/12/2024, 17:01:34 |
HW1 out | |
|
Dear students, HW1 is now out. Due date is 23/12. I recommend starting soon. In particular, it is good to start with Question 1.1 parts (a) and (b) before next week's lesson. For Question 1.5, it might help to wait until after tomorrow's lesson. As a reminder, submission in pairs is allowed. Your submissions should be typed, ideally in LaTeX. Enjoy! David |
| עדכון אחרון ב-2/12/2024, 09:36:10 Last updated on 2/12/2024, 09:36:10 Последняя модификация2/12/2024, 09:36:10 تمت الحتلنة الأخيرة ب-2/12/2024, 09:36:10 |
Back to in-person lectures (Taub 3) | |
|
Dear Students, As you may have seen, the Technion has announced that classes are moving back to in-person format. Therefore, our lectures will move to their originally scheduled location, in Taub 3. Looking forward to even more interactive lectures! Wishing us a quiet and enjoyable rest of the semester. Best, David |
| עדכון אחרון ב-30/11/2024, 19:20:03 Last updated on 30/11/2024, 19:20:03 Последняя модификация30/11/2024, 19:20:03 تمت الحتلنة الأخيرة ب-30/11/2024, 19:20:03 |
Today's office hours + Lecture 3 Whiteboard | |
|
Dear students, Today's office hours will not take place in person. If you want to meet (possibly at a later time) to ask me questions, please email me and we can schedule a zoom meeting. On another note: thanks for another interactive lesson. The whiteboard for lecture 3 has been added to added to the course material. The topics from the lecture notes not covered in class in detail provide more practice / examples of tricks seen in previous lectures. Wishing us all a quiet rest of the week, David |
| פורסם ב-26/11/2024, 12:41:19 Created on 26/11/2024, 12:41:19 Создано26/11/2024, 12:41:19 تم النشر ب-26/11/2024, 12:41:19 |
Lecture 2 whiteboard + addition to lecture 1 | |
|
Dear students, The whiteboard from yesterday's lecture (Lecture 2) was uploaded. Thanks to the students who attended and participated, and thanks for the votes on preferred proofs of Lemma 1. For Lecture 1, the construction of k-wise independent hash functions presented was insufficient for our needs, since we require to map elements in [m] to a much smaller range [2/eps] (thanks Michael for pointing this out!) The fix is fairly simple, and effectively boils down to taking remainders modulo the size of the smaller range. See the updated slides (especially the text in blue). For those who haven't checked this out yet, I remind you that the end of Lecture 1's slides have a numeric example to provide some explanation of why these kind of sketching algorithms are so popular in practice. (In short: these algorithms provide savings of several orders of magnitude in space!) Best, David |
| עדכון אחרון ב-20/11/2024, 13:12:58 Last updated on 20/11/2024, 13:12:58 Последняя модификация20/11/2024, 13:12:58 تمت الحتلنة الأخيرة ب-20/11/2024, 13:12:58 |
Lecture 2 notes | |
|
Dear students, The notes for today's lecture have been updated (minor change of flow of the lecture). If you use the notes during class, do make sure to download the most recent notes. See you soon, David |
| פורסם ב-19/11/2024, 09:24:40 Created on 19/11/2024, 09:24:40 Создано19/11/2024, 09:24:40 تم النشر ب-19/11/2024, 09:24:40 |
Lecture 1 notes | |
|
Dear students, Please note that the notes for Lecture 1 now include: (1) a discussion of the Reservoir Sampling algorithm we saw in the last ten minutes of class. (2) a quick numerical example and discussion explaining the popularity in practice of streaming algorithms. (Thanks for Adar for pointing out that (1) wasn't actually uploaded, and asking about (2).) Best, David |
| עדכון אחרון ב-14/11/2024, 15:44:11 Last updated on 14/11/2024, 15:44:11 Последняя модификация14/11/2024, 15:44:11 تمت الحتلنة الأخيرة ب-14/11/2024, 15:44:11 |
Extra office hours to questions regarding the first lecture | |
|
Dear students, To help students who missed the first lecture and were worried about making up the missed material, I will hold an exceptional extra office hour this week on Thursday 11:00-12:00 for clarification questions regarding the first lecture (see course material). If you cannot attend this extra office hour and missed the first lesson, you are strongly recommended to attend my office hour next Tuesday an hour after class. (Email me if meeting over Zoom for the office hour is easier.) As a reminder: for the second lecture, make sure to go over HW0 for a probability refresher. Best, David |
| עדכון אחרון ב-13/11/2024, 10:58:19 Last updated on 13/11/2024, 10:58:19 Последняя модификация13/11/2024, 10:58:19 تمت الحتلنة الأخيرة ب-13/11/2024, 10:58:19 |
Lecture 1 summary: | |
|
Dear Students, Thanks to the students who came to the first lecture and contributed to an interactive and engaging lesson. I hope you enjoyed the discussion. Following the lesson, I uploaded the lecture whiteboard and updated the notes to include an appendix on Reservoir Sampling. Looking forward to seeing you in the next lectures. (To best prepare: please finish HW0 and go over Lecture 1, especially if you missed it.) Best, David |
| עדכון אחרון ב-12/11/2024, 14:33:00 Last updated on 12/11/2024, 14:33:00 Последняя модификация12/11/2024, 14:33:00 تمت الحتلنة الأخيرة ب-12/11/2024, 14:33:00 |
Welcome to Foundations of Algorithms for Massive Datasets! | |
|
Dear students, Welcome to the course. I'm looking forward to discussing some elegant algorithms (and lower bounds) for massive data. See the course syllabus for tentative topics. We may cover these in less detail and also cover other topics. As per current Technion regulations, we will have our classes *over zoom*. See course syllabus for the zoom room link and some tips and requests to make lectures as interactive (and effective) as possible given the circumstances. To prepare for the first few lessons, I uploaded a *non-mandatory HW0*. This homework is intended as a reminder of some basic probabilistic tools that you have seen before and we will use in the course. It is recommended you do at least parts (a) and (b) before the first lecture, and the other parts before Lecture 2. Looking forward to seeing you in (virtual) class, and wishing us all a productive and quiet semester! Best, David |
| עדכון אחרון ב-6/11/2024, 18:35:23 Last updated on 6/11/2024, 18:35:23 Последняя модификация6/11/2024, 18:35:23 تمت الحتلنة الأخيرة ب-6/11/2024, 18:35:23 |