The Informational Complexity of Learning from Examples

This thesis attempts to quantify the amount of information needed to learn certain tasks. The tasks chosen vary from learning functions in a Sobolev space using radial basis function networks to learning grammars in the principles and parameters framework of modern linguistic theory. These problems are analyzed from the perspective of computational learning theory and certain unifying perspectives emerge.

Complexity of Human Language Comprehension

The goal of this article is to reveal the computational structure of modern principle-and-parameter (Chomskian) linguistic theories: what computational problems do these informal theories pose, and what is the underlying structure of those computations? To do this, I analyze the computational complexity of human language comprehension: what linguistic representation is assigned to a given sound? This problem is factored into smaller, interrelated (but independently statable) problems. For example, in order to understand a given sound, the listener must assign a phonetic form to the sound; determine the morphemes that compose the words in the sound; and calculate the linguistic antecedent of every pronoun in the utterance. I prove that these and other subproblems are all NP-hard, and that language comprehension is itself PSPACE-hard.

Investigation of aspect ratio of hole drilling from micro to nanoscale via focused ion beam fine milling

Holes with different sizes from microscale to nanoscale were directly fabricated by focused ion beam (FIB) milling in this paper. Maximum aspect ratio of the fabricated holes can be 5:1 for the hole with large size with pure FIB milling, 10:1 for gas assistant etching, and 1:1 for the hole with size below 100 nm. A phenomenon of volume swell at the boundary of the hole was observed. The reason maybe due to the dose dependence of the effective sputter yield in low intensity Gaussian beam tail regions and redeposition. Different materials were used to investigate variation of the aspect ratio. The results show that for some special material, such as Ni-Be, the corresponding aspect ratio can reach 13.8:1 with Cl₂ assistant etching, but only 0.09:1 for Si(100) with single scan of the FIB.

Room-temperature continuous-wave operation of GaInNAs/GaAs quantum dot laser with GaAsN barrier grown by solid source molecular beam epitaxy

We present the results of GaInNAs/GaAs quantum dot structures with GaAsN barrier layers grown by solid source molecular beam epitaxy. Extension of the emission wavelength of GaInNAs quantum dots by ~170nm was observed in samples with GaAsN barriers in place of GaAs. However, optimization of the GaAsN barrier layer thickness is necessary to avoid degradation in luminescence intensity and structural property of the GaInNAs dots. Lasers with GaInNAs quantum dots as active layer were fabricated and room-temperature continuous-wave lasing was observed for the first time. Lasing occurs via the ground state at ~1.2μm, with threshold current density of 2.1kA/cm[superscript 2] and maximum output power of 16mW. These results are significantly better than previously reported values for this quantum-dot system.

The Complexity of Safety Stock Placement in General-Network Supply Chains

We consider the optimization problem of safety stock placement in a supply chain, as formulated in [1]. We prove that this problem is NP-Hard for supply chains modeled as general acyclic networks. Thus, we do not expect to find a polynomial-time algorithm for safety stock placement for a general-network supply chain.