Black-Box Algorithm Synthesis -- Divide-and-Conquer and More

Algorithm synthesis is a newly emerging branch of program synthesis, targeting to automatically apply a predefined class of algorithms to a user-provided program. In algorithm synthesis, one popular topic is to synthesize divide-and-conquer-style parallel programs. Existing approaches on this topic rely on the syntax of the user-provided program and require it to follow a specific format, namely single-pass. In many cases, implementing such a program is still difficult for the user. Therefore, in this paper, we study the black-box synthesis for divide-and-conquer which removes the requirement on the syntax and propose a novel algorithm synthesizer AutoLifter. Besides, we show that AutoLifter can be generalized to other algorithms beyond divide-and-conquer. We propose a novel type of synthesis tasks, namely lifting problems, and show that AutoLifter can be applied to those algorithms where the synthesis task is an instance of lifting problems. To our knowledge, AutoLifter is the first algorithm synthesizer that generalizes across algorithm types. We evaluate AutoLifter on two datasets containing 57 tasks covering five different algorithms. The results demonstrate the effectiveness of AutoLifter for solving lifting problems and show that though AutoLifter does not access the syntax of the user-provided program, it still achieves competitive performance compared with white-box approaches for divide-and-conquer.