Mak, Yan Kei. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 59-63). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.6 / Chapter 1.1 --- Historical background --- p.6 / Chapter 1.2 --- Why study communication complexity? --- p.7 / Chapter 1.3 --- Main ideas and results --- p.8 / Chapter 1.4 --- Recent development --- p.12 / Chapter 1.5 --- Structure of the thesis --- p.12 / Chapter 2 --- Deterministic Communication Complexity --- p.13 / Chapter 2.1 --- Definitions --- p.13 / Chapter 2.2 --- Tiling lower bound --- p.16 / Chapter 2.3 --- Fooling set lower bound --- p.21 / Chapter 2.4 --- Rank lower bound --- p.24 / Chapter 2.5 --- Comparison of the bounds --- p.27 / Chapter 3 --- Nondeterministic Communication Complexity --- p.29 / Chapter 3.1 --- Definitions --- p.29 / Chapter 3.2 --- "Gaps between N0(f), N1(f) and D(f)" --- p.31 / Chapter 3.3 --- Aho-Ullman-Yannakakis Theorem --- p.33 / Chapter 4 --- Randomized Communication Complexity --- p.38 / Chapter 4.1 --- Preliminaries --- p.38 / Chapter 4.2 --- Definitions --- p.39 / Chapter 4.3 --- Error reduction --- p.41 / Chapter 4.4 --- Exponential gap with D(f) --- p.42 / Chapter 4.5 --- The public coin model --- p.44 / Chapter 4.6 --- Distributional complexity --- p.46 / Chapter 5 --- Communication Complexity Classes --- p.51 / Chapter 5.1 --- Basic classes --- p.51 / Chapter 5.2 --- Polynomial-time hierarchy --- p.52 / Chapter 5.3 --- Reducibility and completeness --- p.53 / Chapter 6 --- Further topics --- p.56 / Chapter 6.1 --- Quantum communication complexity --- p.56 / Chapter 6.2 --- More techniques for bounds --- p.57 / Chapter 6.3 --- Complexity of communication complexity --- p.57 / Bibliography --- p.59

This thesis expands on the notion of linear complexity for a graph as defined by Michael Orrison and David Neel in their paper "The Linear Complexity of a Graph." It considers additional classes of graphs and provides upper bounds for additional types of graphs and graph operations.

Kolmogorov complexity is a theory based on the premise that the complexity of a binary string can be measured by its compressibility; that is, a string’s complexity is the length of the shortest program that produces that string. We explore applications of this measure to graph theory.

Thesis (Ph. D.)--University of Chicago, Dept. of Computer Science, June 1999. / Includes bibliographical references. Also available on the Internet.

In the first part of the thesis we show black-box separations in public and private-key cryptography. Our main result answers in the negative the question of whether we can base Identity Based Encryption (IBE) on Trapdoor Permutations. Furthermore, we make progress towards the black-box separation of IBE from the Decisional Diffie-Hellman assumption. We also show the necessity of adaptivity when querying one-way permutations to construct pseudorandom generators a' la Goldreich-Levin; an issue related to streaming models for cryptography. In the second part we introduce streaming techniques in understanding randomness in efficient computation, proving lower bounds for efficiently computable problems, and in computing cryptographic primitives. We observe [Coo71] that logarithmic space-bounded Turing Machines, equipped with an unbounded stack, henceforth called Stack Machines, together with an external random tape of polynomial length characterize RP,BPP an so on. By parametrizing on the number of passes over the random tape we provide a technical perspective bringing together Streaming, Derandomization, and older works in Stack Machines. Our technical developments relate this new model with previous works in derandomization. For example, we show that to derandomize parts of BPP it is in some sense sufficient to derandomize BPNC (a class believed to be much lower than P \subseteq BPP). We also obtain a number of results for variants of the main model, regarding e.g. the fooling power of Nisan's pseudorandom generator (PRG) [N92] for the derandomization of BPNC^1, and the relation of parametrized access to NP-witnesses with width-parametrizations of SAT. A substantial contribution regards a streaming approach to lower bounds for problems in the NC-hierarchy (and above). We apply Communication Complexity to show a streaming lower bound for a model with an unbounded (free-to-access) pushdown storage. In particular, we obtain a $n^{\Omega(1)}$ lower bound simultaneously in the space and in the number of passes over the input, for a variant of inner product. This is the first lower bound for machines that correspond to poly-size circuits, can do Parity, Barrington's language, and decide problems in P-NC assuming EXP \neq PSPACE. Finally, we initiate the study of log-space streaming computation of cryptographic primitives. We observe that the work on Cryptography in NC^0 [AIK08] yields a non-black-box construction of a one-way function computable in an O(log n)-space bounded streaming model.Also, we show that relying on this work is in some sense necessary.

Parameterized complexity theory relaxes the classical notion of tractability and allows to solve some classically hard problems in a reasonably efficient way. However, many problems of interest remain intractable in the context of parameterized complexity. A completeness theory to categorize such problems has been developed based on problems on circuits and Model Checking problems. Although a basic machine characterization was proposed, it was not explored any further. We develop a computational view of parameterized complexity theory based on resource-bounded programs that run on alternating random access machines. We develop both natural and normalized machine characterizations for the W[t] and L[t] classes. Based on the new characterizations, we derive the basic completeness results in parameterized complexity theory, from a computational perspective. Unlike the previous cases, our proofs follow the classical approach for showing basic NP-completeness results (Cook's Theorem, in particular). We give new proofs of the Normalization Theorem by showing that (i) the computation of a resource-bounded program on an alternating RAM can be represented by instances of corre- sponding basic parametric problems, and (ii) the basic parametric problems can be decided by programs respecting the corresponding resource bounds. Many of the fundamental results follow as a consequence of our new proof of the Normalization Theorem. Based on a natural characterization of the W[t] classes, we develop new structural results establishing relationships among the classes in the W-hierarchy, and the W[t] and L[t] classes. Nontrivial upper-bound beyond the second level of the W-hierarchy is quite uncommon. We make use of the ability to implement natural algorithms to show new upper bounds for several parametric problems. We show that Subset Sum, Maximal Irredundant Set, and Reachability Distance in Vector Addition Systems (Petri Nets) are in W[3], W[4], and W[5], respectively. In some cases, the new bounds result in new completeness results. We derive new lower bounds based on the normalized programs for the W[t] and L[t] classes. We show that Longest Common Subsequence, with parameter the number of strings, is hard for L[t], t >= 1, and for W[SAT]. We also show that Precedence Constrained Multiprocessor Scheduling, with parameter the number of processors, is hard for L[t], t >= 1.

In the first part of the thesis we show black-box separations in public and private-key cryptography. Our main result answers in the negative the question of whether we can base Identity Based Encryption (IBE) on Trapdoor Permutations. Furthermore, we make progress towards the black-box separation of IBE from the Decisional Diffie-Hellman assumption. We also show the necessity of adaptivity when querying one-way permutations to construct pseudorandom generators a' la Goldreich-Levin; an issue related to streaming models for cryptography. In the second part we introduce streaming techniques in understanding randomness in efficient computation, proving lower bounds for efficiently computable problems, and in computing cryptographic primitives. We observe [Coo71] that logarithmic space-bounded Turing Machines, equipped with an unbounded stack, henceforth called Stack Machines, together with an external random tape of polynomial length characterize RP,BPP an so on. By parametrizing on the number of passes over the random tape we provide a technical perspective bringing together Streaming, Derandomization, and older works in Stack Machines. Our technical developments relate this new model with previous works in derandomization. For example, we show that to derandomize parts of BPP it is in some sense sufficient to derandomize BPNC (a class believed to be much lower than P \subseteq BPP). We also obtain a number of results for variants of the main model, regarding e.g. the fooling power of Nisan's pseudorandom generator (PRG) [N92] for the derandomization of BPNC^1, and the relation of parametrized access to NP-witnesses with width-parametrizations of SAT. A substantial contribution regards a streaming approach to lower bounds for problems in the NC-hierarchy (and above). We apply Communication Complexity to show a streaming lower bound for a model with an unbounded (free-to-access) pushdown storage. In particular, we obtain a $n^{\Omega(1)}$ lower bound simultaneously in the space and in the number of passes over the input, for a variant of inner product. This is the first lower bound for machines that correspond to poly-size circuits, can do Parity, Barrington's language, and decide problems in P-NC assuming EXP \neq PSPACE. Finally, we initiate the study of log-space streaming computation of cryptographic primitives. We observe that the work on Cryptography in NC^0 [AIK08] yields a non-black-box construction of a one-way function computable in an O(log n)-space bounded streaming model.Also, we show that relying on this work is in some sense necessary.

Parameterized complexity theory relaxes the classical notion of tractability and allows to solve some classically hard problems in a reasonably efficient way. However, many problems of interest remain intractable in the context of parameterized complexity. A completeness theory to categorize such problems has been developed based on problems on circuits and Model Checking problems. Although a basic machine characterization was proposed, it was not explored any further. We develop a computational view of parameterized complexity theory based on resource-bounded programs that run on alternating random access machines. We develop both natural and normalized machine characterizations for the W[t] and L[t] classes. Based on the new characterizations, we derive the basic completeness results in parameterized complexity theory, from a computational perspective. Unlike the previous cases, our proofs follow the classical approach for showing basic NP-completeness results (Cook's Theorem, in particular). We give new proofs of the Normalization Theorem by showing that (i) the computation of a resource-bounded program on an alternating RAM can be represented by instances of corre- sponding basic parametric problems, and (ii) the basic parametric problems can be decided by programs respecting the corresponding resource bounds. Many of the fundamental results follow as a consequence of our new proof of the Normalization Theorem. Based on a natural characterization of the W[t] classes, we develop new structural results establishing relationships among the classes in the W-hierarchy, and the W[t] and L[t] classes. Nontrivial upper-bound beyond the second level of the W-hierarchy is quite uncommon. We make use of the ability to implement natural algorithms to show new upper bounds for several parametric problems. We show that Subset Sum, Maximal Irredundant Set, and Reachability Distance in Vector Addition Systems (Petri Nets) are in W[3], W[4], and W[5], respectively. In some cases, the new bounds result in new completeness results. We derive new lower bounds based on the normalized programs for the W[t] and L[t] classes. We show that Longest Common Subsequence, with parameter the number of strings, is hard for L[t], t >= 1, and for W[SAT]. We also show that Precedence Constrained Multiprocessor Scheduling, with parameter the number of processors, is hard for L[t], t >= 1.

A major open problem in complexity theory is to determine whether randomized complexity classes such as BPP, AM, and MA have any nontrivial derandomization. This thesis investigates the derandomization of two randomized versions of the polynomial hierarchy.

A major open problem in complexity theory is to determine whether randomized complexity classes such as BPP, AM, and MA have any nontrivial derandomization. This thesis investigates the derandomization of two randomized versions of the polynomial hierarchy.