Completions of epsilon-dense partial Latin squares

A classical question in combinatorics is the following: given a partial Latin square $P$, when can we complete $P$ to a Latin square $L$? In this paper, we investigate the class of textbf{$epsilon$-dense partial Latin squares}: partial Latin squares in which each symbol, row, and column contains no more than $epsilon n$-many nonblank cells. Based on a conjecture of Nash-Williams, Daykin and H"aggkvist conjectured that all $frac{1}{4}$-dense partial Latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random Latin squares, and use this novel technique to study $ epsilon$-dense partial Latin squares that contain no more than $delta n^2$ filled cells in total.

In Chapter 2, we construct completions for all $ epsilon$-dense partial Latin squares containing no more than $delta n^2$ filled cells in total, given that $epsilon < frac{1}{12}, delta < frac{ left(1-12epsilonright)^{2}}{10409}$. In particular, we show that all $9.8 cdot 10^{-5}$-dense partial Latin squares are completable. In Chapter 4, we augment these results by roughly a factor of two using some probabilistic techniques. These results improve prior work by Gustavsson, which required $epsilon = delta leq 10^{-7}$, as well as Chetwynd and H"aggkvist, which required $epsilon = delta = 10^{-5}$, $n$ even and greater than $10^7$.

If we omit the probabilistic techniques noted above, we further show that such completions can always be found in polynomial time. This contrasts a result of Colbourn, which states that completing arbitrary partial Latin squares is an NP-complete task. In Chapter 3, we strengthen Colbourn's result to the claim that completing an arbitrary $left(frac{1}{2} + epsilonright)$-dense partial Latin square is NP-complete, for any $epsilon > 0$.

Colbourn's result hinges heavily on a connection between triangulations of tripartite graphs and Latin squares. Motivated by this, we use our results on Latin squares to prove that any tripartite graph $G = (V_1, V_2, V_3)$ such that begin{itemize} item $|V_1| = |V_2| = |V_3| = n$, item For every vertex $v in V_i$, $deg_+(v) = deg_-(v) geq (1- epsilon)n,$ and item $|E(G)| > (1 - delta)cdot 3n^2$ end{itemize} admits a triangulation, if $epsilon < frac{1}{132}$, $delta < frac{(1 -132epsilon)^2 }{83272}$. In particular, this holds when $epsilon = delta=1.197 cdot 10^{-5}$.

This strengthens results of Gustavsson, which requires $epsilon = delta = 10^{-7}$.

In an unrelated vein, Chapter 6 explores the class of textbf{quasirandom graphs}, a notion first introduced by Chung, Graham and Wilson cite{chung1989quasi} in 1989. Roughly speaking, a sequence of graphs is called "quasirandom"' if it has a number of properties possessed by the random graph, all of which turn out to be equivalent. In this chapter, we study possible extensions of these results to random $k$-edge colorings, and create an analogue of Chung, Graham and Wilson's result for such colorings.

Topics in randomized numerical linear algebra

This thesis studies three classes of randomized numerical linear algebra algorithms, namely: (i) randomized matrix sparsification algorithms, (ii) low-rank approximation algorithms that use randomized unitary transformations, and (iii) low-rank approximation algorithms for positive-semidefinite (PSD) matrices.

Randomized matrix sparsification algorithms set randomly chosen entries of the input matrix to zero. When the approximant is substituted for the original matrix in computations, its sparsity allows one to employ faster sparsity-exploiting algorithms. This thesis contributes bounds on the approximation error of nonuniform randomized sparsification schemes, measured in the spectral norm and two NP-hard norms that are of interest in computational graph theory and subset selection applications.

Low-rank approximations based on randomized unitary transformations have several desirable properties: they have low communication costs, are amenable to parallel implementation, and exploit the existence of fast transform algorithms. This thesis investigates the tradeoff between the accuracy and cost of generating such approximations. State-of-the-art spectral and Frobenius-norm error bounds are provided.

The last class of algorithms considered are SPSD "sketching" algorithms. Such sketches can be computed faster than approximations based on projecting onto mixtures of the columns of the matrix. The performance of several such sketching schemes is empirically evaluated using a suite of canonical matrices drawn from machine learning and data analysis applications, and a framework is developed for establishing theoretical error bounds.

In addition to studying these algorithms, this thesis extends the Matrix Laplace Transform framework to derive Chernoff and Bernstein inequalities that apply to all the eigenvalues of certain classes of random matrices. These inequalities are used to investigate the behavior of the singular values of a matrix under random sampling, and to derive convergence rates for each individual eigenvalue of a sample covariance matrix.

Variable-angle electron spectroscopic studies of various polyatomic molecular systems

The complementary techniques of low-energy, variable-angle electron-impact spectroscopy and ultraviolet variable-angle photoelectron spectroscopy have been used to study the electronic spectroscopy and structure of several series of molecules. Electron-impact studies were performed at incident beam energies between 25 eV and 100 eV and at scattering angles ranging from 0° to 90°. The energy-loss regions from 0 eV to greater than 15 eV were studied. Photoelectron spectroscopic studies were conducted using a HeI radiation source and spectra were measured at scattering angles from 45° to 90°. The molecules studied were chosen because of their spectroscopic, chemical, and structural interest. The operation of a new electron-impact spectrometer with multiple-mode target source capability is described. This spectrometer has been used to investigate the spin-forbidden transitions in a number of molecular systems.

The electron-impact spectroscopy of the six chloro-substituted ethylenes has been studied over the energy-loss region from 0-15 eV. Spin-forbidden excitations corresponding to the π → π*, N → T transition have been observed at excitation energies ranging from 4.13 eV in vinyl chloride to 3.54 eV in tetrachloroethylene. Symmetry-forbidden transitions of the type π → np have been oberved in trans-dichloroethyene and tetrachlor oethylene. In addition, transitions to many states lying above the first ionization potential were observed for the first time. Many of these bands have been assigned to Rydberg series converging to higher ionization potentials. The trends observed in the measured transition energies for the π → π*, N → T, and N → V as well as the π → 3s excitation are discussed and compared to those observed in the methyl- and fluoro- substituted ethylenes.

The electron energy-loss spectra of the group VIb transition metal hexacarbonyls have been studied in the 0 eV to 15 eV region. The differential cross sections were obtained for several features in the 3-7 eV energy-loss region. The symmetry-forbidden nature of the ¹A_1g → ¹A_1g, 2t_2g(π) → 3t_2g(π*) transition in these compounds was confirmed by the high-energy, low-angle behavior of their relative intensities. Several low lying transitions have been assigned to ligand field transitions on the basis of the energy and angular behavior of the differential cross sections for these transitions. No transitions which could clearly be assigned to singlet → triplet excitations involving metal orbitals were located. A number of states lying above the first ionization potential have been observed for the first time. A number of features in the 6-14 eV energy-loss region of the spectra of these compounds correspond quite well to those observed in free CO.

A number of exploratory studies have been performed. The π → π*, N → T, singlet → triplet excitation has been located in vinyl bromide at 4.05 eV. We have also observed this transition at approximately 3.8 eV in a cis-/trans- mixture of the 1,2-dibromoethylenes. The low-angle spectrum of iron pentacarbonyl was measured over the energy-loss region extending from 2-12 eV. A number of transitions of 8 eV or greater excitation energy were observed for the first time. Cyclopropane was also studied at both high and low angles but no clear evidence for any spin- forbidden transitions was found. The electron-impact spectrum of the methyl radical resulting from the pyrolysis of tetramethyl tin was obtained at 100 eV incident energy and at 0° scattering angle. Transitions observed at 5.70 eV and 8.30 eV agree well with the previous optical results. In addition, a number of bands were observed in the 8-14 eV region which are most likely due to Rydberg transitions converging to the higher ionization potentials of this molecule. This is the first reported electron-impact spectrum of a polyatomic free radical.

Variable-angle photoelectron spectroscopic studies were performed on a series of three-membered-ring heterocyclic compounds. These compounds are of great interest due to their highly unusual structure. Photoelectron angular distributions using HeI radiation have been measured for the first time for ethylene oxide and ethyleneimine. The measured anisotropy parameters, β, along with those measured for cyclopropane were used to confirm the orbital correlations and photoelectron band assignments. No high values of β similar to those expected for alkene π orbitals were observed for the Walsh or Forster-Coulson-Moffit type orbitals.

The power of quantum Fourier sampling

How powerful are Quantum Computers? Despite the prevailing belief that Quantum Computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's famous factoring algorithm [Shor97] gives an example of a problem that can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring, however, is unlikely to be NP-Hard, meaning that few unexpected formal consequences would arise, should such a classical algorithm be discovered. Could it then be the case that any quantum algorithm can be simulated efficiently classically? Likewise, could it be the case that Quantum Computers can quickly solve problems much harder than factoring? If so, where does this power come from, and what classical computational resources do we need to solve the hardest problems for which there exist efficient quantum algorithms?

We make progress toward understanding these questions through studying the relationship between classical nondeterminism and quantum computing. In particular, is there a problem that can be solved efficiently on a Quantum Computer that cannot be efficiently solved using nondeterminism? In this thesis we address this problem from the perspective of sampling problems. Namely, we give evidence that approximately sampling the Quantum Fourier Transform of an efficiently computable function, while easy quantumly, is hard for any classical machine in the Polynomial Time Hierarchy. In particular, we prove the existence of a class of distributions that can be sampled efficiently by a Quantum Computer, that likely cannot be approximately sampled in randomized polynomial time with an oracle for the Polynomial Time Hierarchy.

Our work complements and generalizes the evidence given in Aaronson and Arkhipov's work [AA2013] where a different distribution with the same computational properties was given. Our result is more general than theirs, but requires a more powerful quantum sampler.