Mohammad Hajiaghayi<p>🚀 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.</p><p>📺 First lecture: <a href="https://youtu.be/Tnm-8xieqB4" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/Tnm-8xieqB4</span><span class="invisible"></span></a><br />🎥 Weekly uploads: Wednesdays at 7 PM EDT. Playlist: <a href="https://youtube.com/playlist?list=PLx7SjCaKZzEIeJxOlTuXveAE5eY7WOYB9" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="ellipsis">youtube.com/playlist?list=PLx7</span><span class="invisible">SjCaKZzEIeJxOlTuXveAE5eY7WOYB9</span></a></p><p>Plus, all 4 previous courses (Game Theory, Algorithms, Lower Bounds, Data Science) are online! 🌐 <a href="https://youtube.com/@hajiaghayi" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtube.com/@hajiaghayi</span><span class="invisible"></span></a></p><p><a href="https://mathstodon.xyz/tags/NetworkDesign" class="mention hashtag" rel="tag">#<span>NetworkDesign</span></a> <a href="https://mathstodon.xyz/tags/Optimization" class="mention hashtag" rel="tag">#<span>Optimization</span></a> <a href="https://mathstodon.xyz/tags/NPComplete" class="mention hashtag" rel="tag">#<span>NPComplete</span></a> <a href="https://mathstodon.xyz/tags/Algorithms" class="mention hashtag" rel="tag">#<span>Algorithms</span></a> <a href="https://mathstodon.xyz/tags/DataScience" class="mention hashtag" rel="tag">#<span>DataScience</span></a> <a href="https://mathstodon.xyz/tags/NeuralNets" class="mention hashtag" rel="tag">#<span>NeuralNets</span></a></p>
Recent searches
No recent searches
Search options
Only available when logged in.
mathstodon.xyz is one of the many independent Mastodon servers you can use to participate in the fediverse.
A Mastodon instance for maths people. We have LaTeX rendering in the web interface!
Administered by:
Server stats:
2.8Kactive users
mathstodon.xyz: About · Status · Profiles directory · Privacy policy
Mastodon: About · Get the app · Keyboard shortcuts · View source code · v4.3.7
#NPComplete
0 posts · 0 participants · 0 posts today
Mohammad Hajiaghayi<p>In our effort to put courses online, we continue lectures on Algorithmic Lower Bound Course. Now you can watch</p><p>Lesson 4-11: Algorithmic Lower Bounds by Mohammad Hajiaghayi - NP-Completeness and Beyond</p><p>(FEEL FREE TO SUBSCRIBE TO YOUTUBE @hajiaghayi FOR FUTURE LESSONS Premiering on WEDNESDAYS)</p><p><a href="https://youtu.be/VZyffnAb1r0" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/VZyffnAb1r0</span><span class="invisible"></span></a> (Lesson 4: 3-Partition Problem & Proving NP-Hardness)</p><p><a href="https://youtu.be/4fCD9_1eQw0" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/4fCD9_1eQw0</span><span class="invisible"></span></a> (Lesson 5: Puzzle Problem NP-Hardness & 3-Partition)</p><p><a href="https://youtu.be/FIyEj72-UJQ" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/FIyEj72-UJQ</span><span class="invisible"></span></a> (Lesson 6: 3-SAT Problem & Proving NP-Hardness)</p><p><a href="https://youtu.be/tbSJzaKx2pA" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/tbSJzaKx2pA</span><span class="invisible"></span></a> (Lesson 7: Puzzle Problem NP-Hardness via 3-SAT)</p><p><a href="https://youtu.be/voRVebBsh94" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/voRVebBsh94</span><span class="invisible"></span></a> (Lesson 8: Fine-grained Subcubic Complexity: Part 1)</p><p><a href="https://youtu.be/gRURSM6QARo" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/gRURSM6QARo</span><span class="invisible"></span></a> (Lesson 9: Fine-grained Subcubic Complexity: Part 2)</p><p><a href="https://youtu.be/qPw82bTAXkc" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/qPw82bTAXkc</span><span class="invisible"></span></a> (Lesson 10: Fine-grained Subquadratic Complexity 1)</p><p><a href="https://youtu.be/C6j4avVkI7U" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/C6j4avVkI7U</span><span class="invisible"></span></a> (Lesson 11: Fine-grained Subquadratic Complexity 2)</p><p><a href="https://mathstodon.xyz/tags/AlorithmicComplexity" class="mention hashtag" rel="tag">#<span>AlorithmicComplexity</span></a>, </p><p><a href="https://mathstodon.xyz/tags/3SAT" class="mention hashtag" rel="tag">#<span>3SAT</span></a>,</p><p><a href="https://mathstodon.xyz/tags/3Partition" class="mention hashtag" rel="tag">#<span>3Partition</span></a>,</p><p><a href="https://mathstodon.xyz/tags/subquadratic" class="mention hashtag" rel="tag">#<span>subquadratic</span></a>,</p><p><a href="https://mathstodon.xyz/tags/subcubic" class="mention hashtag" rel="tag">#<span>subcubic</span></a>,</p><p><a href="https://mathstodon.xyz/tags/Finegrained" class="mention hashtag" rel="tag">#<span>Finegrained</span></a>,</p><p><a href="https://mathstodon.xyz/tags/HardnessExploration" class="mention hashtag" rel="tag">#<span>HardnessExploration</span></a>, </p><p><a href="https://mathstodon.xyz/tags/NP" class="mention hashtag" rel="tag">#<span>NP</span></a>, </p><p><a href="https://mathstodon.xyz/tags/PSPACE" class="mention hashtag" rel="tag">#<span>PSPACE</span></a>, </p><p><a href="https://mathstodon.xyz/tags/NPComplete" class="mention hashtag" rel="tag">#<span>NPComplete</span></a>, </p><p><a href="https://mathstodon.xyz/tags/LogSpace" class="mention hashtag" rel="tag">#<span>LogSpace</span></a>, </p><p><a href="https://mathstodon.xyz/tags/ExponentialComplexity" class="mention hashtag" rel="tag">#<span>ExponentialComplexity</span></a>, </p><p><a href="https://mathstodon.xyz/tags/ParallelComputation" class="mention hashtag" rel="tag">#<span>ParallelComputation</span></a>, </p><p><a href="https://mathstodon.xyz/tags/PvsNP" class="mention hashtag" rel="tag">#<span>PvsNP</span></a>, </p><p><a href="https://mathstodon.xyz/tags/NPSPACE" class="mention hashtag" rel="tag">#<span>NPSPACE</span></a>, </p><p><a href="https://mathstodon.xyz/tags/NonDeterministicSpace" class="mention hashtag" rel="tag">#<span>NonDeterministicSpace</span></a>, hashtag</p><p><a href="https://mathstodon.xyz/tags/SavitchTheorem" class="mention hashtag" rel="tag">#<span>SavitchTheorem</span></a>, </p><p><a href="https://mathstodon.xyz/tags/ComplexityClasses" class="mention hashtag" rel="tag">#<span>ComplexityClasses</span></a>, </p><p><a href="https://mathstodon.xyz/tags/Reductions" class="mention hashtag" rel="tag">#<span>Reductions</span></a>, </p><p><a href="https://mathstodon.xyz/tags/ImportantProblems" class="mention hashtag" rel="tag">#<span>ImportantProblems</span></a>, </p><p><a href="https://mathstodon.xyz/tags/CommunicationComplexity" class="mention hashtag" rel="tag">#<span>CommunicationComplexity</span></a>, hashtag</p><p><a href="https://mathstodon.xyz/tags/GeometricProblems" class="mention hashtag" rel="tag">#<span>GeometricProblems</span></a>, </p><p><a href="https://mathstodon.xyz/tags/AlgorithmDesign" class="mention hashtag" rel="tag">#<span>AlgorithmDesign</span></a>, </p><p><a href="https://mathstodon.xyz/tags/ComputationalComplexity" class="mention hashtag" rel="tag">#<span>ComputationalComplexity</span></a>, </p><p><a href="https://mathstodon.xyz/tags/TheoreticalComputerScience" class="mention hashtag" rel="tag">#<span>TheoreticalComputerScience</span></a>, </p><p><a href="https://mathstodon.xyz/tags/AlgorithmicLowerBounds" class="mention hashtag" rel="tag">#<span>AlgorithmicLowerBounds</span></a></p><p>For comprehensive handwritten lecture notes on this course, visit the instructor's website:</p><p><a href="http://www.cs.umd.edu/~hajiagha/" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">http://www.</span><span class="">cs.umd.edu/~hajiagha/</span><span class="invisible"></span></a><br />The course textbook "Computational Intractability: A Guide to Algorithmic Lower Bounds" by Demaine, Gasarch, and Hajiaghayi is available for free at:</p><p><a href="https://hardness.mit.edu/" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">hardness.mit.edu/</span><span class="invisible"></span></a></p>
Victor Porton<p>My P=NP proof - check for errors<br /><a href="https://drive.google.com/file/d/16Ws_eZF8f-rn1mFvkIT-UdMdvTwOu4vO/view?usp=drive_link" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="ellipsis">drive.google.com/file/d/16Ws_e</span><span class="invisible">ZF8f-rn1mFvkIT-UdMdvTwOu4vO/view?usp=drive_link</span></a><br />It uses inversions of bijections, algorithms as arguments to other algorithms, reducing SAT to another NP problem, incompleteness of ZFC.<br />If you find it hard to read, give me advice how to make it more clear.<br />And no, I don't provide a practically efficient NP-complete algorithm. <a href="https://mathstodon.xyz/tags/pnp" class="mention hashtag" rel="tag">#<span>pnp</span></a> <a href="https://mathstodon.xyz/tags/NPComplete" class="mention hashtag" rel="tag">#<span>NPComplete</span></a></p>
mhe<p>Is this NP-complete?</p><p><a href="https://mathstodon.xyz/tags/NPComplete" class="mention hashtag" rel="tag">#<span>NPComplete</span></a> <a href="https://mathstodon.xyz/tags/texel" class="mention hashtag" rel="tag">#<span>texel</span></a> <a href="https://mathstodon.xyz/tags/netherlands" class="mention hashtag" rel="tag">#<span>netherlands</span></a></p>
Bornach<p><a href="https://masto.ai/tags/BingChat" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>BingChat</span></a> (precise) has concluded that P=NP</p><p>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.</p><p>In both cases it claimed polynomial time complexity to solve an NP-hard problem</p><p><a href="https://masto.ai/tags/ComputerScience" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>ComputerScience</span></a> <a href="https://masto.ai/tags/complexity" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>complexity</span></a> <a href="https://masto.ai/tags/PequalsNP" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>PequalsNP</span></a> <a href="https://masto.ai/tags/NPhard" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>NPhard</span></a> <a href="https://masto.ai/tags/NPcomplete" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>NPcomplete</span></a> <a href="https://masto.ai/tags/python" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>python</span></a> <a href="https://masto.ai/tags/GraphTheory" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>GraphTheory</span></a></p>
Bornach<p>[Up and Atom] on the unsolved problem of whether NP-Complete problems can be decided in polynomial time<br><a href="https://youtu.be/ctwX--JEzSA" rel="nofollow noopener noreferrer" target="_blank"><span class="invisible">https://</span><span class="">youtu.be/ctwX--JEzSA</span><span class="invisible"></span></a><br><a href="https://masto.ai/tags/mathematics" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>mathematics</span></a> <a href="https://masto.ai/tags/ComputerScience" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>ComputerScience</span></a> <a href="https://masto.ai/tags/computability" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>computability</span></a> <a href="https://masto.ai/tags/ComplexityTheory" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>ComplexityTheory</span></a> <a href="https://masto.ai/tags/NPComplete" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>NPComplete</span></a></p>
Lup Yuen Lee 李立源<p><a href="https://qoto.org/tags/Kingdomino" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>Kingdomino</span></a> is <a href="https://qoto.org/tags/NPComplete" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>NPComplete</span></a>...</p><p><a href="https://arxiv.org/abs/1909.02849" rel="nofollow noopener noreferrer" target="_blank"><span class="invisible">https://</span><span class="">arxiv.org/abs/1909.02849</span><span class="invisible"></span></a></p>
SearchLive feeds
Mastodon is the best way to keep up with what's happening.
Follow anyone across the fediverse and see it all in chronological order. No algorithms, ads, or clickbait in sight.
Create accountLoginDrag & drop to upload