Algorithm Synthesis --- Automatic Application of Algorithmic Paradigms
Host
Armando Solar-Lezama
CSAIL Alliance Program (CAP)
Title: Algorithm Synthesis --- Automatic Application of Algorithmic Paradigms
Abstract: Efficiency is a core pursuit of software development, and designing efficient algorithms is the fundamental way to achieve it. Though many algorithm design paradigms have been proposed, such as divide-and-conquer and dynamic programming, applying these algorithmic paradigms is still difficult. In this talk, I will describe the newest progress of Peking University for automating the application of algorithm design paradigms. Concretely, we have discovered a new program synthesis problem, namely the lifting problem, to which the applications of multiple algorithm paradigms reduce to. We design a program synthesis approach to the lifting problem, AutoLifter, and implemented a set of synthesizers for different algorithmic paradigms. In the experiments, our approach solves 83 of 96 algorithmic problems, outperforming existing synthesizers for specific algorithmic paradigms.
Bio: Yingfei Xiong obtained his Ph.D. degree from the University of Tokyo in 2009, and worked as a postdoctoral researcher at University of Waterloo from 2009 to 2011. He joined Peking University in 2012 and is currently an associate professor. His research interest is programming languages and software engineering in general, and program synthesis, repair, and analysis in particular. He proposed theories and approaches to reduce the cost of writing and repairing programs. For example, delta-based BX is one of the most widely-used bidirectional transformation frameworks; the data-driven program synthesis framework, L2S, and its application to program repair, ACS and Recoder, significantly improves the precision and recall of program repair. His work was adopted by the industry, such as a new Linux kernel project, Yancloud DaaS, ZTE, etc. He received CCF-IEEE CS Young Scientist Award, the 10 Year Most Influential Paper Award at MODELS, 5 ACM SIGSOFT/IEEE TCSE Distinguished Paper Awards. He served as PC in top conferences such as ICSE, FSE, PLDI.
Abstract: Efficiency is a core pursuit of software development, and designing efficient algorithms is the fundamental way to achieve it. Though many algorithm design paradigms have been proposed, such as divide-and-conquer and dynamic programming, applying these algorithmic paradigms is still difficult. In this talk, I will describe the newest progress of Peking University for automating the application of algorithm design paradigms. Concretely, we have discovered a new program synthesis problem, namely the lifting problem, to which the applications of multiple algorithm paradigms reduce to. We design a program synthesis approach to the lifting problem, AutoLifter, and implemented a set of synthesizers for different algorithmic paradigms. In the experiments, our approach solves 83 of 96 algorithmic problems, outperforming existing synthesizers for specific algorithmic paradigms.
Bio: Yingfei Xiong obtained his Ph.D. degree from the University of Tokyo in 2009, and worked as a postdoctoral researcher at University of Waterloo from 2009 to 2011. He joined Peking University in 2012 and is currently an associate professor. His research interest is programming languages and software engineering in general, and program synthesis, repair, and analysis in particular. He proposed theories and approaches to reduce the cost of writing and repairing programs. For example, delta-based BX is one of the most widely-used bidirectional transformation frameworks; the data-driven program synthesis framework, L2S, and its application to program repair, ACS and Recoder, significantly improves the precision and recall of program repair. His work was adopted by the industry, such as a new Linux kernel project, Yancloud DaaS, ZTE, etc. He received CCF-IEEE CS Young Scientist Award, the 10 Year Most Influential Paper Award at MODELS, 5 ACM SIGSOFT/IEEE TCSE Distinguished Paper Awards. He served as PC in top conferences such as ICSE, FSE, PLDI.