The goal of this project is to study efficient separator and randomization theories and technologies with applications to algorithm design. Separator and randomization are basic tools of designing algorithms for many applications problems. A separator is often used to decompose a difficult computational problem into smaller and easier ones, and then to solve the problem with a divide and conquer strategy. Randomization is widely used to speed up computation by sampling a small number of cases from a large number of possibilities. In order to attack challenging computational problems, such as protein 3D structure prediction, more efficient decomposition methods are expected to be developed. This project unifies the two approaches of separators and randomization because of their close connection. This unified approach helps the development of sublinear time algorithms, which are usually based on random sampling.
The decomposition methods are studied from low dimensional geometric spaces to high dimensional spaces and to general graphs and to algebraic computation. Proving the existence of a separator will get new insights into combinatorial nature of a given problem. Finding a separator efficiently is also an interesting algorithmic problem itself and often uses randomized methods. On the other hand, the research on complexity theory related to randomness is a part of this project, which includes the research about some lower bounds for randomization methods and the limitation of derandomization. A potential application of separator theory is protein folding prediction. A more efficient decomposition method will bring faster algorithm for this significant problem in science. As this project combines decomposition with randomization, the results of the research make new contributions to the core area of computation theory and discover applications in the field of bioinformatics. Education is an integral part of this project. Minority graduate students and female graduate students are involved in the protein 3D structure related algorithm design and web-server implementation. A randomized computation course for both undergraduate and graduate students is developed.
