My area of research can be broadly defined as high-performance computation in discrete domains. This area includes algorithms for minimization, decomposition, and other transformations of boolean/multi-valued functions and networks, finite state machines, and other discrete objects. The methods I develop, alone or in collaboration, have applications in the development of CAD tools for logic synthesis, verification, design for test, combinatorial optimization, and other areas of computer science and engineering, as well as in datamining, robotics, and artificial intelligence.
While working in this area, it is impossible to approach research from the theoretical stand-point only. In addition to developing new algorithms using paper-and-pencil, a good deal of time is spent programming these algorithms to prove their efficiency and practical usefulness. This, in turn, requires studying the data structures and accounting for them in the algorithms. For this reason, decision diagrams (DDs), an efficient way of representing and manipulating discrete functions, plays an important role in my research. I specialize in developing DD-based algorithms and converting classical algorithms into a form when DDs can be used to solve them, which typically lead to major speed-ups compared to other implementations.
When the algorithms and data structures are ready, it is time to write software. My choice is for C/C++, which goes with a lot of software libraries and packages to make development process fast and effiicient. But programming is not the end of research, because the proof-of-concept requires demonstration that the program performs well on the given set of benchmarks. This last step, too, often requires a lot of creativity, because having the tool may be not enough. It is important to know what options to use and how to pre- or post-process the results to get the optimum performance, which may eventually lead back to redesigning the tool. The same chicken and egg situation we observe in other areas.
I tried, in a glance, to show that my area of research has several equally important components (developing theory, creating algorithms, adjusting the algorithms to the data structures and vice versa, developing sofware, testing software using benchmarks, fine-tuning software, and visualizing the results). Because of this long lists, it is difficult to classify my research contributions. Some of them fall into several categories and can be considered from different points of view. This webpage attempts to introduce a structure for a set of research results defying structurization.
Alan Mishchenko's Home Page