Topics in Algorithms and Complexity

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

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.