CS- 6515-A: Intro to Grad Algorithms - CS-6515-A

Handwritten notes:

https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m91zg1908zt2bq

Recording:

https://mediaspace.gatech.edu/media/CS6515%20L21%20Reductions/1_8ak9rdvh

Further reading/material

• A slightly different reduction. Instead of padding the vector with 0s as we did in class, they shift the vectors a bit.
  • Introduction of section 2. https://arxiv.org/pdf/2110.10283
  • Lemma 1 is a reduction for the same Nearest Neighbor problem
• Introductory chapter of a course on Fine-grained complexity theory
  • https://www.mpi-inf.mpg.de/fileadmin/inf/d1/teaching/summer19/finegrained/lec1.pdf
  • Defines the same concepts, but uses a different example (NFA acceptance instead of Nearest Neighbor search)

Problem set 9 (problems 25,26,27) available here, and under the resource tab:

https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m91umk2h4w660a

The last question (reduction) can be done via programming.

Test cases & templates are under the resource tab and here:

Test cases: https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m91z9b5f3e1638

Code template: https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m91z9ojx2sc6n1

Due date is Thursday April 10th.

The following is the tentative schedule for the next month. The general topics are:

• Reductions
• Randomized Algorithms

Reductions will not be about P/NP. The focus will be on efficient algorithms, i.e., constructing some algorithm when you have blackbox access to another fast algorithm. 

The schedule below is likely to shift a bit as some topics could take longer or shorter than planned.

Tue 04/01 Reductions & OV-problem (this was last tuesday @470)

Thu 04/03 Exam 3 + release HW9

Tue 04/08 Reductions for matrix multiplication & triangle detection

Thu 04/10 Schwarz Zippel & algebraic algorithm for matching + release HW10 (likely only 2 problems)

Tue 04/15 One sided error & Amplification

Thu 04/17 Global Min Cut (Randomized) Last lecture.

Tue 04/22 No lecture. We will have the makeup exam for those with excused absence for exam 1, 2 or 3.

Thu 04/24 No lecture. (finals week)

Tue 04/29 Exam 4 (cumulative, all topics)

Hey everyone, due to the weather I will also be moving my office hours online today. The link is: https://meet.google.com/scz-anmv-htw

Hey everyone,

 

Problem set 7 grades were released earlier today. You should be able to see your grade and any comments left by the graders on Gradescope. These are the statistics:

 

Rubric and Regrade Requests

 

Your graders are human, and so they may have made errors. If you think your assignment was graded incorrectly against the rubric, then make a regrade request to the instructors on Gradescope. Regrades will be open for SIX days until April 3rd at 11:59 PM (04-3-2025 @ 11:59 PM ET). Please submit a regrade before the deadline. Also, provide a brief explanation of the issue(s) and why you should receive points.

Some notes about regrade requests:

• Please read the rubric closely and use the solutions for reference before submitting a regrade request. 
• Note that we formally reserve the right to regrade your entire submission if you submit a regrade request. It is possible, though very unlikely, to end up losing points from submitting a regrade request.
• Regrade requests without an explanation of the issue/why points should be returned will be dismissed. 
• Note that regrades requests are for when you think the grading did not match the rubric, or if you think that the answer in the rubric is incorrect. Please do not submit a regrade request if you were graded correctly but feel that the rubric is unfair.

Handwritten notes:

https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m8rughy1sv414o

Recording:

https://mediaspace.gatech.edu/media/CS6515%20L20%20Gradient%20Descent%20II/1_f6qw5mb3

Bubeck's optimization book http://sbubeck.com/Bubeck15.pdf

• Section 3.2 is on smooth functions
• Section 3.4.2 is on smooth & strongly convex functions

We did not complete the proof of convergence for Lipschitz functions.

Here are the handwritten notes that I had prepared for class, if you are interested in the proof.

https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m8rughk8b4s143

Handwritten notes: https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m8p04vvxw9h7nv

Recording: https://mediaspace.gatech.edu/media/CS%206515%20L19%20Gradient%20Descent%20I/1_e490et6i

Other material:

• Bubeck's convex optimization book, in particular section 3.2 http://sbubeck.com/Bubeck15.pdf (Theorem 3.3 and Lemma 3.4 are the same as in class, but the proof for 3.3 is a bit different.)

I would like to share this message from GT's Competitive Programming club:

GT Competitive Programming club is hosting our first GTCP Competition, which will be held on the Friday after spring break on March 28 at 3-6pm. It will be held at CoC 101.   It will be in teams of two and we will be giving prizes and medals to the top teams, as well as featuring your resumes to our sponsors, which include Google, IMC Trading, Millenium, AMD, and VISA. Grab your friends and sign up for the competition! There will be dinner served after the contest as well.   Sign up now at https://tinyurl.com/gtcp2025

GTCP_2025_Poster_1.pdf

If there are any questions about the competition and/or club, please contact professor Abrahim Ladha abrahimladha@gatech.edu who is the club advisor.

Since many of the techniques are relevant to this course (DP, D&C, etc) and we've also had similar programming homework questions, I've decided to count participation in the contest as one optional homework problem. (i.e., equivalent to scoring 20/20 points on one HW problem)

Remark: We continue to use the top 21 homework problems for the final grade. Skipping the contest will not negatively affect your grade.