Randomized computation has become one of the major research fields in Computer Science since its emergence in the late 1970's. In spite of its seemingly enhanced power, as far as we know, randomness may not provide any computational advantage (by more than a polynomial factor) over determinism. The first objective of this project is to investigate the issue of reducing randomness in computation via explicit combinatorial constructions.
Derandomization in space-bounded computation is the major subject to study here, with the focus on pseudorandom generator constructions. In particular, the constructions of pseudorandom generators for constant-width read-once branching programs, and of discrepancy sets for combinatorial rectangles are to be examined.
Derandomizing the well-known randomized log-space algorithm for undirected graph connectivity problem will be investigated further. In the meantime, a variant of the connectivity problem in the model of directed graphs with tree structures will also be examined, hoping this can provide a better understanding of the relationship between non-deterministic and deterministic computations.
An advanced topic course (graduate or undergraduate) on explicit combinatorial constructions and their applications will be designed. The goal of the course is to enable the students to attain a solid understanding of the mathematical foundation of explicit constructions as well as their applications to algorithm design and computational complexity.
Mobile computing over wireless channels has emerged as a rapidly growing technology and gained a large amount of attention in recent years. The highly asymmetric nature of the communication environment in this context gives rise to many new challenges concerning the issues of information dissemination and retrieval. Indexed data scheduling is to design data broadcast schemes that minimize both the average waiting time and energy consumption of the clients in retrieving information on air. Another objective of this project is to investigate the possibility of applying the ideas from indexed data scheduling to the design of communication protocols for multimedia applications in wireless mobile communication networks.
