The Taub Faculty of Computer Science Events and Talks

Substantial efforts have been devoted into improving the capabilities of neural networks to solve algorithmic tasks. Through training, these networks learn to mimic algorithmic behaviour, enabling them to handle tasks such as sorting, navigating, and managing complex data structures like graphs. However, classic algorithms and neural networks are fundamentally different, making it challenging to analyze the complexity of an algorithm learned by a neural network. First, it is necessary to establish that the model has indeed learned an abstract solution resembling algorithmic behaviour. Additionally, while the complexity of classic algorithms is measured asymptotically, the complexity of an algorithm learned by a neural network must be measured within the finite input space supported by the model. This evaluation should also factor into consideration potential degradation in the model’s accuracy on unseen data. To this end, we will discuss these challenges and their implications, and propose methods for measuring the complexity of algorithms learned by neural networks. Finally, we will present experimental results on graph problems.