Tractability in structured problems

点击翻译按钮获取中文摘要

The idea of structuring information is at the heart of computational problems in diverse application areas such as social sciences, artificial intelligence, biology, Web computing, and many other areas. There may be restrictions in the way that information can be structured, either due to the types of inputs to the problems (the types of information on which the problem is being solved) or due to the type of solution being sought. The goal of my research program is to determine ways of characterizing structure that allows for efficient solutions to fundamental problems; these in turn can be applied to specific problems in target areas. My interests range from extracting structure from problems to developing characterizations and associated solutions, especially for fundamental problems of broad applicability across areas.