Aspects of Computation Theory and Logic

主要研究有限模型理论中的广泛问题，这是研究一阶逻辑及其在有限结构集合上的扩展的主题。他试图发现具有不动点算子的逻辑在有限结构集合上捕获计算复杂性类的充分必要条件。此外，他还研究了一阶逻辑在作为渐近测度为1的有限结构的集合上的扩展的比较表达能力。他还研究了具有固定有限变量数的逻辑的各个方面，包括可满足性的算法，以及在这种逻辑中可表达的性质的渐近概率。这些问题的进展将加强逻辑和计算之间的联系，并加强逻辑学、计算复杂性和渐近组合学之间的相互作用。在不同的方向上，他继续致力于在整数规划框架内开发组合优化的结构近似理论。本研究的目的是识别具有性能保证的近似算法的大类NP优化问题

The principal investigator works on a broad spectrum of problems in finite model theory, which is the subject that studies first-order logic and its extensions on collections of finite structures. He seeks to discover necessary and sufficient conditions under which logics with fixpoint operators capture computational complexity classes on collections of finite structures. Moreover , he investigates the comparative expressive power of extensions of first-order logic on collections as finite structures of asymptotic measure equal to one. He also studies various aspects of logics with fixed finite number of variables, including algorithms for satisfiability, and asymptotic probabilities of properties expressible in such logics. Progress on these problems will strengthen the connections between logic and computation, and enhance the interaction between logic, computational complexity, and asymptotic combinatorics. In a different direction, He continues working towards the development of a structural approximation theory for combinatorial optimization within the framework of integer programming. The objective of this investigation is to identify large classes of NP optimization problems possesing approximation algorithms with performance guarantees.***