How to train your dragon: on the application of the Metropolis-Hastings algorithm for program synthesis

This paper addresses the problem of Inductive Synthesis by analysing the Metropolis-Hastings stochastic search algorithm. The goal of Inductive Synthesis is to generate programs whose intended behaviour is established through the use of input and output examples. The Metropolis-Hastings algorithm searches the set of all possible programs and finds possible solutions. Our experiments show that while optimization can be done under certain conditions, it does not improve the algorithm’s success rate in synthesizing programs on complex domains compared to more randomized but domainspecific approaches.CSE3000 Research ProjectComputer Science and Engineerin