Complexity Theory

Photo by Shubham Dhage on Unsplash

Over the past week, I’ve taken a dive into the Analysis of Algorithms course I’m completing this semester. In hindsight, it may have been a smart choice to take this course closer to learning Discrete Mathematics and Data Structures, when that material was still fresh in my mind. I’m feeling more confident after acclimating for a week of moving through the coursework. There is also starting to be a shift towards coding more in our assignments, which is a welcome change from only working with equations at the beginning of the semester.

Coincidentally, as I’m digging deeper into the coursework, a friend shared the following blog with me about new algorithm research. Discovering Novel Algorithms with AlphaTensor is wild! I hadn’t even considered that algorithm research is an ongoing area of scientific study until now. Of course we’re all familiar with mathematicians of the past and all their textbook-worthy contributions. However, new research on math and algorithms is far less visible.

Computational Complexity Theory is the study of solving computational problems with algorithms, in terms of the resources required. Of special interest, especially to those in computer science, is finding the most efficient and fastest algorithms to solve problems. AlphaTensor is an artificial intelligence (AI) developed with the goal of finding efficient and provably correct algorithms for solving demanding computations. The amazing result is an AI which can consistently discover new algorithms for matrix multiplication which are more efficient than those designed by humans. This is an automated system which is expanding the boundaries of what is thought to be possible in mathematics research using AI and Machine Learning. I would highly recommend anyone remotely interested should read the post, which is not too long, but is full of incredible information about the research being performing regarding solving computational problems with new technology.