Topics in Algorithms and Complexity

这项研究涉及到算法和复杂性的主要领域。在图同构测试中，寻找有效地解决几种已知易处理情况的统一的顺序和并行算法，特别是具有有界价或特征值多重数的图类，将被统一。在通信复杂性方面，将研究确定性模型和概率模型中的具体问题。除了VLSI中通信复杂度对AT2复杂度的标准应用外，本项目还将考虑应用于下界问题。在可学习性理论中，我们将调查不同学习协议的语言课程的学习情况。将考虑学习有限自动机、马尔科夫链以及确定性的一个反自动机的算法的可能扩展及其局限性。

This research concerns main areas of algorithms and complexity. In graph isomorphism testing, a search for unifying sequential and parallel algorithms solving efficiently several of the known tractable cases, in particular the classes of graphs with bounded valence or eigenvalue multiplicity, will be unitiated. In communication complexity, specific problems in the deterministic and probabilistic models will be investigated. Besides the standard application of communication complexity to the AT2 complexity in VLSI, this project will also consider applications to lower bound problems. In learnabiliy theory, the kearning of language classes for a variety of learning protocols will be investigated. Possible extensions and their limitations of algorithms for learning finite automata, Marcov chains, as well as deteministic one counter automata will be considered.