Lower bounds on parallel, distributed and automata computations
Mihály Geréb-Graus · 1989
In this thesis we present a collection of lower bound results from several areas of computer science. Conventional wisdom states that lower bounds are much more difficult to prove than upper bounds. To get an upper bound one has to demonstrate just one scheme with the appropriate complexity. On the other hand, to prove lower bounds one has to deal with all possible schemes. The difficulty of lower bounds can be further demonstrated by the fact that wherever for some problem we have a very large gap between the lower and the upper bound, the conjecture for the truth usually is the known upper bound. Our first two results are impossibility results for finite state automata. A hierarchy of complexity classes on tree languages (analogous to the polynomial hierarchy) accepted by alternating finite state machines is introduced. It turns out that the alternating class is equal to the well known tree language class accepted by the treeautomata. By separating the deterministic and the nondeterministic classes of our hierarchy we give a negative answer to the folklore question whether the expressive power of the treeautomata is the same as that of the finite state automaton that can walk on the edges of the tree (bugautomaton). We prove that three-head one-way DFA cannot perform string-matching, that is, no three-head one-way DFA accepts the language L = $\{$x#y $\vert$ x is a substring of y, where x,y $\in$ $\{$0,1$\}$$\sp{\rm *}$$\}$. We prove that in a one round fair coin flipping (or voting) scheme with n participants, there is at least one participant who has a chance to decide the outcome with probability at least 3/n $-$ o(1/n). We prove an optimal lower bound on the average time required by any algorithm that merges two sorted lists on the parallel comparison tree model. We present a proof of a negative answer for a question raised by Skyum and Valiant, namely, whether the class of symmetric boolean functions has a p-complete family. We give a combinatorial characterization for the concept classes learnable from negative (or positive) examples only in the so-called distribution free learning model. Blumer et al. (BEHW) gave a combinatorial characterization for the sample complexity of a learning algorithm using the so called Vapnik-Chervonenkis dimension. Our result is analogous to this result for the one-sided error case.