Parallel time and space are perhaps the two most fundamental resources in computation. They appear to be orthogonal, as reducing one potentially increases the other. Surprisingly there are some nice duality relations between them, where their roles can be switched. However, space alone seems to be a more powerful resource than parallel time alone, as information can only flow unidirectional in time, and the duality relation is known to fail in some circumstance. Our research shows that, when information is only allowed to flow in some restricted but natural fashion, this discrepancy disappears and more duality relations emerge [C1, C2]. This seems to suggest that some deep relation between time and space exists that governs all these.
Randomness is another useful computational resource. There are several important problems for which the most efficient algorithms known are randomized. However, randomized algorithms typically depend on the availability of a perfect random source, whose existence even in nature is debatable. So if possible, we would like to convert randomized algorithms into deterministic ones. We study how to remove randomness in cases when space [C3] or parallel time [C4] is limited in some way. We also study how the derandomization of probabilistic nondeterministic computation is related to the nondeterminism versus determinism problem and the sequential time versus space problem [C5].
In addition to time, space, and randomness, sometimes different measures can also capture the hardness of functions and provide different perspectives. This is the case for symmetric functions in complexity classes corresponding to various constant-depth circuits. We show that symmetric functions in qAC^{0} [2] can be characterized by their so-called spectra [C6]. Analogous characterizations are also known for symmetric functions in qAC^{0} and qPERCEPTRON.
[C1] David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, and Sven Skyum, Searching constant width mazes captures the AC^{0}-hierarchy, in Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, pp. 73--83, 1998.¡@
[C2] David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, and Sven Skyum, On monotone plannar circuits, in Proceedings of the 14th Annual IEEE Conference on Computational Complexity, pp. 24--31, 1999.
[C3] Chi-Jen Lu, Improved pseudorandom generators for combinatorial rectangles, accepted by Combinatorica, preliminary version in Proceedings of the 25th International Colloquium on Automata, Languages, and Programming, pp. 223--234, 1998.
[C4] Chi-Jen Lu, Deterministic hypergraph coloring and its applications, in Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 35--46, 1998.
[C5] Chi-Jen Lu, Derandomizing Arthur-Merlin games under uniform assumptions, in Proceedings of the 11th Annual International Symposium on Algorithms And Computation, pp. 302--312, 2000.
[C6] Chi-Jen Lu, An exact characterization of symmetric functions in qAC^{0}[2], to appear in Theoretical Computer Science, 261(2), 2001, preliminary version in Proceedings of the 4th Annual International Computing and Combinatorics Conference, pp. 167--173, 1998.