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 qAC0 [2] can be
characterized by their so-called spectra [C6]. Analogous characterizations are
also known for symmetric functions in qAC0
and qPERCEPTRON.
4. Selected Results:
[C1] David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, and Sven Skyum, Searching constant width mazes captures the AC0-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 qAC0[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.