Studying the approximation threshold of NP-hard optimization problems, i.e. the ratio of the objective value achievable by a polynomial time algorithm to that of the optimal solution is an important field in theoretical computer science. In the past two decades there has been significant development both in terms of finding good approximation algorithms, e.g. through the use of semidefinite programming and hardness of approximation, e.g. the development of Probabilistically Checkable Proofs and Unique Games Conjecture. Trying to prove lower bounds for the approximation threshold of an optimization problem, one could take one of two approaches. In the first approach, one proves such lower bounds under a complexity assumption like P =/= NP or Unique Games Conjecture. In the second approach, one studies the behaviour of prominent algorithmic schemes, such as Linear Programming (LP) and Semidefinite Programming (SDP) relaxations for the problem of interest. There, the measure of efficiency is the integrality gap which sets the approximation limitation of the algorithms based on these relaxations. In this work we study the integrality gap of families of strong LP and SDP relaxations for a number of combinatorial optimization problems. The relaxations come from the context of Lift-and-Project systems. There one starts from a standard (weak) relaxation from a problem and iteratively adds more constraints to make the relaxation stronger, i.e. closer to an exact formulation of the problem. We mostly study the performance of the Sherali-Adams SDP relaxations. Specifically, the main contributions of this thesis are as follows. • We show optimal integrality gaps for the level-\Theta(n) Sherali-Adams SDP relaxation of MAX k-CSP_q(P) for any predicate P:[q]^k -> {0,1} satisfying a technical condition, which we call being promising. Our result show that for such predicates MAX k-CSP_q (P) cannot be approximated (beyond a trivial approximation) by the Sherali-Adams SDP relaxations of even very high level. Austrin and Håstad (SIAM J. Comput., 2011) show that a random predicate is almost surely promising. • We complement the above result by showing that for some class of predicates which are not promising MAX k-CSP_q(P) can be approximated (beyond the trivial approximation) by its canonical SDP relaxation. • We show optimal integrality gap lower bounds for level-poly(n) Sherali-Adams SDP relaxations of Quadratic Programming. We also present superconstant integrality gap lower bounds for superconstant levels of the same hierarchy for MaxCutGain. • We show optimal integrality gap lower bounds for the level-5 Sherali-Adams SDP relaxation of Vertex Cover. We also conjecture a positivity condition on the Taylor expansion of a certain function which, if proved, shows optimal integrality gaps for any constant level of the Sherali-Adams SDP hierarchy for Vertex Cover. • We revisit the connection between integrality gap lower bounds and the Frankl-Rödl theorem (Trans. of the AMS, 1987). We prove a new density version of that theorem which can be interpreted as a new isoperimetric inequality of the Hamming cube. Using this inequality we prove integrality gap lower bounds for the Lovász-Schrijver SDP (resp. Sherali-Adams LP) relaxation of Vertex Cover (resp. Independent Set) in degree bounded graphs.

We first present a novel approach to sketching 2D curves with minimally varying curvature as piecewise clothoids. A stable and efficient algorithm fits a sketched piecewise linear curve using a number of clothoid segments with G2 continuity based on a specified error tolerance. We then present a system for conceptually sketching 3D layouts for road and other path networks. Our system makes four key contributions. First, we generate paths with piecewise linear curvature by fitting 2D clothoid curves to strokes sketched on a terrain. Second, the height of paths above the terrain is automatically determined using a new constraint optimization formulation of the occlusion relationships between sketched strokes. Third, we present the break-out lens, a novel widget inspired by break-out views used in engineering visualization, to facilitate the in-context and interactive manipulation of paths from alternate view points. Finally, our path construction is terrain sensitive.

We first present a novel approach to sketching 2D curves with minimally varying curvature as piecewise clothoids. A stable and efficient algorithm fits a sketched piecewise linear curve using a number of clothoid segments with G2 continuity based on a specified error tolerance. We then present a system for conceptually sketching 3D layouts for road and other path networks. Our system makes four key contributions. First, we generate paths with piecewise linear curvature by fitting 2D clothoid curves to strokes sketched on a terrain. Second, the height of paths above the terrain is automatically determined using a new constraint optimization formulation of the occlusion relationships between sketched strokes. Third, we present the break-out lens, a novel widget inspired by break-out views used in engineering visualization, to facilitate the in-context and interactive manipulation of paths from alternate view points. Finally, our path construction is terrain sensitive.

Studying the approximation threshold of NP-hard optimization problems, i.e. the ratio of the objective value achievable by a polynomial time algorithm to that of the optimal solution is an important field in theoretical computer science. In the past two decades there has been significant development both in terms of finding good approximation algorithms, e.g. through the use of semidefinite programming and hardness of approximation, e.g. the development of Probabilistically Checkable Proofs and Unique Games Conjecture. Trying to prove lower bounds for the approximation threshold of an optimization problem, one could take one of two approaches. In the first approach, one proves such lower bounds under a complexity assumption like P =/= NP or Unique Games Conjecture. In the second approach, one studies the behaviour of prominent algorithmic schemes, such as Linear Programming (LP) and Semidefinite Programming (SDP) relaxations for the problem of interest. There, the measure of efficiency is the integrality gap which sets the approximation limitation of the algorithms based on these relaxations. In this work we study the integrality gap of families of strong LP and SDP relaxations for a number of combinatorial optimization problems. The relaxations come from the context of Lift-and-Project systems. There one starts from a standard (weak) relaxation from a problem and iteratively adds more constraints to make the relaxation stronger, i.e. closer to an exact formulation of the problem. We mostly study the performance of the Sherali-Adams SDP relaxations. Specifically, the main contributions of this thesis are as follows. • We show optimal integrality gaps for the level-\Theta(n) Sherali-Adams SDP relaxation of MAX k-CSP_q(P) for any predicate P:[q]^k -> {0,1} satisfying a technical condition, which we call being promising. Our result show that for such predicates MAX k-CSP_q (P) cannot be approximated (beyond a trivial approximation) by the Sherali-Adams SDP relaxations of even very high level. Austrin and Håstad (SIAM J. Comput., 2011) show that a random predicate is almost surely promising. • We complement the above result by showing that for some class of predicates which are not promising MAX k-CSP_q(P) can be approximated (beyond the trivial approximation) by its canonical SDP relaxation. • We show optimal integrality gap lower bounds for level-poly(n) Sherali-Adams SDP relaxations of Quadratic Programming. We also present superconstant integrality gap lower bounds for superconstant levels of the same hierarchy for MaxCutGain. • We show optimal integrality gap lower bounds for the level-5 Sherali-Adams SDP relaxation of Vertex Cover. We also conjecture a positivity condition on the Taylor expansion of a certain function which, if proved, shows optimal integrality gaps for any constant level of the Sherali-Adams SDP hierarchy for Vertex Cover. • We revisit the connection between integrality gap lower bounds and the Frankl-Rödl theorem (Trans. of the AMS, 1987). We prove a new density version of that theorem which can be interpreted as a new isoperimetric inequality of the Hamming cube. Using this inequality we prove integrality gap lower bounds for the Lovász-Schrijver SDP (resp. Sherali-Adams LP) relaxation of Vertex Cover (resp. Independent Set) in degree bounded graphs.

One desirable property of machine learning algorithms is the ability to balance the number of parameters in a model in accordance with the amount of available data. Incorporating nonparametric Bayesian priors into models is one approach of automatically adjusting model capacity to the amount of available data: with small datasets, models are less complex (require storing fewer parameters in memory), whereas with larger datasets, models are implicitly more complex (require storing more parameters in memory). Thus, nonparametric Bayesian priors satisfy frequentist intuitions about model complexity within a fully Bayesian framework. This thesis presents several novel machine learning models and applications that use nonparametric Bayesian priors. We introduce two novel models that use flat, Dirichlet process priors. The first is an infinite mixture of experts model, which builds a fully generative, joint density model of the input and output space. The second is a Bayesian biclustering model, which simultaneously organizes a data matrix into block-constant biclusters. The model capable of efficiently processing very large, sparse matrices, enabling cluster analysis on incomplete data matrices. We introduce binary matrix factorization, a novel matrix factorization model that, in contrast to classic factorization methods, such as singular value decomposition, decomposes a matrix using latent binary matrices. We describe two nonparametric Bayesian priors over tree structures. The first is an infinitely exchangeable generalization of the nested Chinese restaurant process that generates data-vectors at a single node in the tree. The second is a novel, finitely exchangeable prior generates trees by first partitioning data indices into groups and then by randomly assigning groups to a tree. We present two applications of the tree priors: the first automatically learns probabilistic stick-figure models of motion-capture data that recover plausible structure and are robust to missing marker data. The second learns hierarchical allocation models based on the latent Dirichlet allocation topic model for document corpora, where nodes in a topic-tree are latent ``super-topics", and nodes in a document-tree are latent categories. The thesis concludes with a summary of contributions, a discussion of the models and their limitations, and a brief outline of potential future research directions.

Whole-genome shotgun sequencing is an experimental technique used for obtaining information about a genome’s sequence, whereby it is broken up into many short (possibly overlapping) segments whose sequence is then determined. A long-standing use of sequencing is in genome assembly – the problem of determining the sequence of an unknown genome, which plays a central role for the sequencing of novel species. However, even within the same species, the genomes of two individuals differ, and though these variations are relatively small, they account for the observed variation in phenotypes. A large portion of these are copy number variants (CNVs), or genomic segments which appear a different number of times in different individuals. The unifying theme of this thesis is the use of genome graphs for both CNV detection and genome assembly problems. Genome graphs, which have already been successfully used for alignment and assembly, capture the structure of a genome even when its sequence is not fully known, as with the case of sequencing data. In this thesis, we extend their uses in several ways, culminating in a method for CNV detection that is based on a novel genome graph model. First, we demonstrate how the double-stranded nature of DNA can be efficiently incorporated into genome graphs by using the technique of bidirected network flow. Furthermore, we show how genome graphs can be efficiently used for finding solutions that maximize the likelihood of the data, as opposed to the usual maximum parsimony approach. Finally, we show how genome graphs can be useful for CNV detection through a novel construction called the donor graph. These extensions are combined into a method for detecting CNVs, which we use on a Yoruban human individual, showing a high degree of accuracy and improvement over previous methods.

Recently there have been several proposals to use redundant execution of diverse replicas to defend against attempts to exploit memory corruption vulnerabilities. However, redundant execution relies on the premise that the replicas behave deterministically, so that if inputs are replicated to both replicas, any divergences in their outputs can only be the result of an attack. Unfortunately, this assumption does not hold for multithreaded programs, which are becoming increasingly prevalent -- the non-deterministic interleaving of threads can also cause divergences in the replicas. This thesis presents a method to eliminate concurrency related non-determinism between replicas. We introduce changes to the existing cache coherence hardware used in multicores to support deterministic redundant execution. We demonstrate that our solution requires moderate hardware changes and shows modest overhead in scientific applications.

Recently there have been several proposals to use redundant execution of diverse replicas to defend against attempts to exploit memory corruption vulnerabilities. However, redundant execution relies on the premise that the replicas behave deterministically, so that if inputs are replicated to both replicas, any divergences in their outputs can only be the result of an attack. Unfortunately, this assumption does not hold for multithreaded programs, which are becoming increasingly prevalent -- the non-deterministic interleaving of threads can also cause divergences in the replicas. This thesis presents a method to eliminate concurrency related non-determinism between replicas. We introduce changes to the existing cache coherence hardware used in multicores to support deterministic redundant execution. We demonstrate that our solution requires moderate hardware changes and shows modest overhead in scientific applications.

One desirable property of machine learning algorithms is the ability to balance the number of parameters in a model in accordance with the amount of available data. Incorporating nonparametric Bayesian priors into models is one approach of automatically adjusting model capacity to the amount of available data: with small datasets, models are less complex (require storing fewer parameters in memory), whereas with larger datasets, models are implicitly more complex (require storing more parameters in memory). Thus, nonparametric Bayesian priors satisfy frequentist intuitions about model complexity within a fully Bayesian framework. This thesis presents several novel machine learning models and applications that use nonparametric Bayesian priors. We introduce two novel models that use flat, Dirichlet process priors. The first is an infinite mixture of experts model, which builds a fully generative, joint density model of the input and output space. The second is a Bayesian biclustering model, which simultaneously organizes a data matrix into block-constant biclusters. The model capable of efficiently processing very large, sparse matrices, enabling cluster analysis on incomplete data matrices. We introduce binary matrix factorization, a novel matrix factorization model that, in contrast to classic factorization methods, such as singular value decomposition, decomposes a matrix using latent binary matrices. We describe two nonparametric Bayesian priors over tree structures. The first is an infinitely exchangeable generalization of the nested Chinese restaurant process that generates data-vectors at a single node in the tree. The second is a novel, finitely exchangeable prior generates trees by first partitioning data indices into groups and then by randomly assigning groups to a tree. We present two applications of the tree priors: the first automatically learns probabilistic stick-figure models of motion-capture data that recover plausible structure and are robust to missing marker data. The second learns hierarchical allocation models based on the latent Dirichlet allocation topic model for document corpora, where nodes in a topic-tree are latent ``super-topics", and nodes in a document-tree are latent categories. The thesis concludes with a summary of contributions, a discussion of the models and their limitations, and a brief outline of potential future research directions.

Whole-genome shotgun sequencing is an experimental technique used for obtaining information about a genome’s sequence, whereby it is broken up into many short (possibly overlapping) segments whose sequence is then determined. A long-standing use of sequencing is in genome assembly – the problem of determining the sequence of an unknown genome, which plays a central role for the sequencing of novel species. However, even within the same species, the genomes of two individuals differ, and though these variations are relatively small, they account for the observed variation in phenotypes. A large portion of these are copy number variants (CNVs), or genomic segments which appear a different number of times in different individuals. The unifying theme of this thesis is the use of genome graphs for both CNV detection and genome assembly problems. Genome graphs, which have already been successfully used for alignment and assembly, capture the structure of a genome even when its sequence is not fully known, as with the case of sequencing data. In this thesis, we extend their uses in several ways, culminating in a method for CNV detection that is based on a novel genome graph model. First, we demonstrate how the double-stranded nature of DNA can be efficiently incorporated into genome graphs by using the technique of bidirected network flow. Furthermore, we show how genome graphs can be efficiently used for finding solutions that maximize the likelihood of the data, as opposed to the usual maximum parsimony approach. Finally, we show how genome graphs can be useful for CNV detection through a novel construction called the donor graph. These extensions are combined into a method for detecting CNVs, which we use on a Yoruban human individual, showing a high degree of accuracy and improvement over previous methods.