Tractability in structured problems

结构化信息的想法是各种应用领域计算问题的核心，例如社会科学、人工智能、生物学、Web计算和许多其他领域。由于问题的输入类型(正在解决问题的信息的类型)或所寻求的解决方案的类型，信息的结构方式可能会受到限制。我的研究计划的目标是确定能够有效解决基本问题的结构特征的方法；这些方法反过来可以应用于目标领域的特定问题。我的兴趣范围从从问题中提取结构到开发表征和相关的解决方案，特别是对于跨领域具有广泛适用性的基本问题。

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.