Computational Complexity

1. Time vs. Space:

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. 

2. Randomness:

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].

3. Spectrum:

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: