Computational Complexity Theory studies the fundamental properties of computation, independent of computational model. Many of its open questions are by now long-standing, having already defied decades of intense attacks by many researchers. One approach towards answering them is to study their counterparts in simpler settings. One such simplification is to replace the Turing machine (our standard formal model of computer) with the two-way finite automaton (essentially, a Turing machine which cannot write on its tape). One can then build a complexity theory, which we call minicomplexity theory, where the analogs of deep open questions like “P vs. NP” and “L vs. NL” remain surprisingly hard. One expects, however, that are still much easier, and that resolving them can provide us with some insight into the original open questions themselves. In this project, our aim is to further develop minicomplexity; to attack some of its central open questions; and to popularize it so that more researchers join its study. This appears to be the first systematic work in Theoretical Computer Science in Qatar and the GCC region in general, which is valuable.