🚀 Excited to announce my 5th course, Network Algorithms and Approximations! 🎓 Explore NP-complete problems (Set Cover, Unique Coverage, etc.), approximation techniques, and applications in data science, neural nets, & network optimization.

📺 First lecture: https://youtu.be/Tnm-8xieqB4
🎥 Weekly uploads: Wednesdays at 7 PM EDT. Playlist: https://youtube.com/playlist?list=PLx7SjCaKZzEIeJxOlTuXveAE5eY7WOYB9

Plus, all 4 previous courses (Game Theory, Algorithms, Lower Bounds, Data Science) are online! 🌐 https://youtube.com/@hajiaghayi

#NetworkDesign #Optimization #NPComplete #Algorithms #DataScience #NeuralNets

In our effort to put courses online, we continue lectures on Algorithmic Lower Bound Course. Now you can watch

Lesson 4-11: Algorithmic Lower Bounds by Mohammad Hajiaghayi - NP-Completeness and Beyond

(FEEL FREE TO SUBSCRIBE TO YOUTUBE @hajiaghayi FOR FUTURE LESSONS Premiering on WEDNESDAYS)

https://youtu.be/VZyffnAb1r0 (Lesson 4: 3-Partition Problem & Proving NP-Hardness)

https://youtu.be/4fCD9_1eQw0 (Lesson 5: Puzzle Problem NP-Hardness & 3-Partition)

https://youtu.be/FIyEj72-UJQ (Lesson 6: 3-SAT Problem & Proving NP-Hardness)

https://youtu.be/tbSJzaKx2pA (Lesson 7: Puzzle Problem NP-Hardness via 3-SAT)

https://youtu.be/voRVebBsh94 (Lesson 8: Fine-grained Subcubic Complexity: Part 1)

https://youtu.be/gRURSM6QARo (Lesson 9: Fine-grained Subcubic Complexity: Part 2)

https://youtu.be/qPw82bTAXkc (Lesson 10: Fine-grained Subquadratic Complexity 1)

https://youtu.be/C6j4avVkI7U (Lesson 11: Fine-grained Subquadratic Complexity 2)

#AlorithmicComplexity,

#3SAT,

#3Partition,

#subquadratic,

#subcubic,

#Finegrained,

#HardnessExploration,

#NP,

#PSPACE,

#NPComplete,

#LogSpace,

#ExponentialComplexity,

#ParallelComputation,

#PvsNP,

#NPSPACE,

#NonDeterministicSpace, hashtag

#SavitchTheorem,

#ComplexityClasses,

#Reductions,

#ImportantProblems,

#CommunicationComplexity, hashtag

#GeometricProblems,

#AlgorithmDesign,

#ComputationalComplexity,

#TheoreticalComputerScience,

#AlgorithmicLowerBounds

For comprehensive handwritten lecture notes on this course, visit the instructor's website:

http://www.cs.umd.edu/~hajiagha/
The course textbook "Computational Intractability: A Guide to Algorithmic Lower Bounds" by Demaine, Gasarch, and Hajiaghayi is available for free at:

https://hardness.mit.edu/

#BingChat (precise) has concluded that P=NP

I asked it to write a Python script that when given a graph where there are no more than 5 edges for every vertex, it returns the length of the longest path that visits each vertex no more than once. Then lifted the edge count restriction.

In both cases it claimed polynomial time complexity to solve an NP-hard problem

#ComputerScience #complexity #PequalsNP #NPhard #NPcomplete #python #GraphTheory

#Kingdomino is #NPComplete...

https://arxiv.org/abs/1909.02849