Programming Puzzles to Teach AI to Code

Adam Tauman Kalai

Recent neural networks such as OpenAI's GPT-3 and Codex appear to have programming abilities well beyond anything seen before. How can one evaluate their performance and leverage these abilities? We introduce a new type of programming challenge called programming puzzles, as an objective and comprehensive evaluation of program synthesis, and release an open-source dataset of Python Programming Puzzles (P3). Each puzzle is defined by a short Python program f, and the goal is to find an input x which makes f output True. The puzzles are objective in that each one is specified entirely by the source code of its verifier f, so evaluating f(x) is all that is needed to test a candidate solution x. The dataset is comprehensive in that it spans problems of a range of difficulties and domains, including classic programming puzzles (e.g., Towers of Hanoi), interview/competitive-programming problems (e.g., dynamic programming), and longstanding open problems in algorithms and mathematics (e.g., factoring). The dataset highlights the strengths of these recent models as well as a way for AI systems to improve at programming through self-training. The talk will cover joint work with Tal Schuster, Matt Bowers, Ashwin Kalyan, Alex Polozov.

  Adam Tauman Kalai is a Senior Principal Researcher at Microsoft Research New England. His research focuses on machine learning, artificial intelligence and algorithms. He received his BA from Harvard and PhD from Carnegie Mellon University. He has served as an Assistant Professor at Georgia Tech and the Toyota Technological Institute at Chicago. He has co-chaired AI and crowdsourcing conferences on machine learning and crowdsourcing including the Conference on Learning Theory (COLT) and the Conference on Human Computation and Crowdsourcing (HCOMP). His honors include multiple best paper awards, an NSF CAREER award, and an Alfred P. Sloan fellowship.