Their paper, titled Lagrange’s Theorem for Binary Squares, shows how to prove theorems in additive number theory using a decision procedure based on finite automata. The research was presented at MFCS’s annual symposium held this year in Liverpool, United Kingdom from August 27–31, 2018.
“Congratulations to Aayush, Jeff and their international colleagues, Parthasarathy Madhusudan and Dirk Nowotka, for receiving the prestigious European Association for Theoretical Computer Science Best Paper Award at MFCS 2018,” said Dan Brown, Director of the David R. Cheriton School of Computer Science. “I saw Aayush give the practice talk for this paper, and I was fascinated by the idea of proving a theorem in number theory using formal language theory, reducing the proof of the theorem to a decidable language problem about finite automata.”
To learn more about this research, please see Parthasarathy Madhusudan, Dirk Nowotka, Aayush Rajasekaran and Jeffrey Shallit. Lagrange’s Theorem for Binary Squares, 2018, arXiv:1710.04247.