Application in Combinatorial Geometry : Heilbronn's Triangle Problem: A-S Ch 3.3, MIT-YZ Ch 3.2,.Turáns Theorem: PB Ch 32, equivalence, proof. Alteration (Sample and Modify): Independent Set: A-S Ch 3.2, M-U 6.4, Heng Guo's Notes,.Lecture 4-5 (Arindam): Probabilistic Methods (Alteration, Second Moment Methods, Concentration Inequalities).More Expectation Method: Balancing Vectors: A-S Thm 2.4.1, MIT-YZ Ch 2.7, Recent Talk by Nikhil Bansal.Derandomization: Max-cut: M-U Lem 6.2, Anna Karlin's Notes, Also see Section 3.4.2 in Survey on Derandomization.Application in Extremal Combinatorics: Erdős-Ko-Rado Theorem: A-S Lemma 1, MIT-YZ Ch 1.4, PB Ch 23.Application in Combinatorial Number Theory: Large Sum-free Set: A-S Thm 1.4.1, MIT-YZ Ch 2.2, Ronitt Rubinfeld's notes.Įfficient Algorithm: Paper by Kolountzakis, Also see SJ Ch 24.3.First use: Ramsey Number Lower Bound: M-U Thm 6.1, A-S Prop 1.1.1, MIT-YZ Ch 1.1, Jacob Fox's notes.Lecture 2-3 (Arindam): Probabilistic Methods (Basics, Expectation Methods).Lecture 1 (Anand/Arindam): Introductory Class: Logistics, Basics of Probability.Please use the materials at your own risk! The course notes posted here will be scribed by students and will not be proof-read or Combinatorial Optimization Related Techniques. Convex Optimization Related Techniques,.The following is a suggestive list of possible With some of the fundamental tools commonly used in this area. This course is intended to equip a student interested in studying theoretical computer science Time: Tuesdays & Thursdays, 11:00 AM-12:30 PM, Online (Teams). E0 206: Theorist's Toolkit, Fall 2020 Instructors: Arindam Khan
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |