• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 501
  • 209
  • 197
  • 136
  • 15
  • Tagged with
  • 1138
  • 734
  • 661
  • 401
  • 401
  • 398
  • 398
  • 398
  • 398
  • 111
  • 102
  • 98
  • 85
  • 83
  • 77
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Sketch-based Path Design

McCrae, James 30 July 2008 (has links)
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.
2

On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems

Benabbas, Siavosh 10 December 2012 (has links)
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.
3

Sketch-based Path Design

McCrae, James 30 July 2008 (has links)
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.
4

On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems

Benabbas, Siavosh 10 December 2012 (has links)
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.
5

Spectral Methods in Extremal Combinatorics

Filmus, Yuval 09 January 2014 (has links)
Extremal combinatorics studies how large a collection of objects can be if it satisfies a given set of restrictions. Inspired by a classical theorem due to Erdos, Ko and Rado, Simonovits and Sos posed the following problem: determine how large a collection of graphs on the vertex set {1,...,n} can be, if the intersection of any two of them contains a triangle. They conjectured that the largest possible collection, containing 1/8 of all graphs, consists of all graphs containing a fixed triangle (a triangle-star). The first major contribution of this thesis is a confirmation of this conjecture. We prove the Simonovits–Sos conjecture in the following strong form: the only triangle-intersecting families of measure at least 1/8 are triangle-stars (uniqueness), and every triangle-intersecting family of measure 1/8−e is O(e)-close to a triangle-star (stability). In order to prove the stability part of our theorem, we utilize a structure theorem for Boolean functions on {0,1}^m whose Fourier expansion is concentrated on the first t+1 levels, due to Kindler and Safra. The second major contribution of this thesis consists of two analogs of this theorem for Boolean functions on S_m whose Fourier expansion is concentrated on the first two levels. In the same way that the Kindler–Safra theorem is useful for studying triangle-intersecting families, our structure theorems are useful for studying intersecting families of permutations, which are families in which any two permutations agree on the image of at least one point. Using one of our theorems, we give a simple proof of the following result of Ellis, Friedgut and Pilpel: an intersecting family of permutations on S_m of size (1−e)(m−1)! is O(e)-close to a double coset, a family which consists of all permutations sending some point i to some point j.
6

Spectral Methods in Extremal Combinatorics

Filmus, Yuval 09 January 2014 (has links)
Extremal combinatorics studies how large a collection of objects can be if it satisfies a given set of restrictions. Inspired by a classical theorem due to Erdos, Ko and Rado, Simonovits and Sos posed the following problem: determine how large a collection of graphs on the vertex set {1,...,n} can be, if the intersection of any two of them contains a triangle. They conjectured that the largest possible collection, containing 1/8 of all graphs, consists of all graphs containing a fixed triangle (a triangle-star). The first major contribution of this thesis is a confirmation of this conjecture. We prove the Simonovits–Sos conjecture in the following strong form: the only triangle-intersecting families of measure at least 1/8 are triangle-stars (uniqueness), and every triangle-intersecting family of measure 1/8−e is O(e)-close to a triangle-star (stability). In order to prove the stability part of our theorem, we utilize a structure theorem for Boolean functions on {0,1}^m whose Fourier expansion is concentrated on the first t+1 levels, due to Kindler and Safra. The second major contribution of this thesis consists of two analogs of this theorem for Boolean functions on S_m whose Fourier expansion is concentrated on the first two levels. In the same way that the Kindler–Safra theorem is useful for studying triangle-intersecting families, our structure theorems are useful for studying intersecting families of permutations, which are families in which any two permutations agree on the image of at least one point. Using one of our theorems, we give a simple proof of the following result of Ellis, Friedgut and Pilpel: an intersecting family of permutations on S_m of size (1−e)(m−1)! is O(e)-close to a double coset, a family which consists of all permutations sending some point i to some point j.
7

Nonparametric Bayesian Methods for Extracting Structure from Data

Meeds, Edward 01 August 2008 (has links)
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.
8

First-order Decision-theoretic Planning in Structured Relational Environments

Sanner, Scott 28 July 2008 (has links)
We consider the general framework of first-order decision-theoretic planning in structured relational environments. Most traditional solution approaches to these planning problems ground the relational specification w.r.t. a specific domain instantiation and apply a solution approach directly to the resulting ground Markov decision process (MDP). Unfortunately, the space and time complexity of these solution algorithms scale linearly with the domain size in the best case and exponentially in the worst case. An alternate approach to grounding a relational planning problem is to lift it to a first-order MDP (FOMDP) specification. This FOMDP can then be solved directly, resulting in a domain-independent solution whose space and time complexity either do not scale with domain size or can scale sublinearly in the domain size. However, such generality does not come without its own set of challenges and the first purpose of this thesis is to explore exact and approximate solution techniques for practically solving FOMDPs. The second purpose of this thesis is to extend the FOMDP specification to succinctly capture factored actions and additive rewards while extending the exact and approximate solution techniques to directly exploit this structure. In addition, we provide a proof of correctness of the first-order symbolic dynamic programming approach w.r.t. its well-studied ground MDP counterpart.
9

Computational Prediction of Target Genes of MicroRNAs

Radfar, Hossein 01 April 2014 (has links)
MicroRNAs (miRNAs) are a class of short (21-25 nt) non-coding endogenous RNAs that mediate the expression of their direct target genes post-transcriptionally. The goal of this thesis is to identify the target genes of miRNAs using computational methods. The most popular computational target prediction methods rely on sequence based determinants to predict targets. However, these determinants are neither sufficient nor necessary to identify functional target sites, and commonly ignore the cellular conditions in which miRNAs interact with their targets \emph{in vivo}. Since miRNAs activity reduces the steady-state abundance of mRNA targets, the main goal of this thesis is to augment large scale gene expression profiles as a supplement to sequence-based computational miRNA target prediction techniques. We develop two computational miRNA target prediction methods: InMiR and BayMiR; in addition, we study the interaction between miRNAs and lncRNAs using long RNA expression data. InMiR is a computational method that predicts the targets of intronic miRNAs based on the expression profiles of their host genes across a large number of datasets. InMiR can also predict which host genes have expression profiles that are good surrogates for those of their intronic miRNAs. Host genes that InMiR predicts are bad surrogates contain significantly more miRNA target sites in their 3 UTRs and are significantly more likely to have predicted Pol II-III promoters in their introns. We also develop BayMiR that scores miRNA-mRNA pairs based on the endogenous footprint of miRNAs on gene expression in a genome-wide scale. BayMiR provides an ``endogenous target repression" index, that identifies the contribution of each miRNA in repressing a target gene in presence of other targeting miRNAs. This thesis also addresses the interactions between miRNAs and lncRNAs. Our analysis on expression abundance of long RNA transcripts (mRNA and lncRNA) shows that the lncRNA target set of some miRNAs have relatively low abundance in the tissues that these miRNAs are highly active. We also found lncRNAs and mRNAs that shared many targeting miRNAs are significantly positively correlated, indicating that these set of highly expressed lncRNAs may act as miRNA sponges to promote mRNA regulation.
10

Computational Prediction of Target Genes of MicroRNAs

Radfar, Hossein 01 April 2014 (has links)
MicroRNAs (miRNAs) are a class of short (21-25 nt) non-coding endogenous RNAs that mediate the expression of their direct target genes post-transcriptionally. The goal of this thesis is to identify the target genes of miRNAs using computational methods. The most popular computational target prediction methods rely on sequence based determinants to predict targets. However, these determinants are neither sufficient nor necessary to identify functional target sites, and commonly ignore the cellular conditions in which miRNAs interact with their targets \emph{in vivo}. Since miRNAs activity reduces the steady-state abundance of mRNA targets, the main goal of this thesis is to augment large scale gene expression profiles as a supplement to sequence-based computational miRNA target prediction techniques. We develop two computational miRNA target prediction methods: InMiR and BayMiR; in addition, we study the interaction between miRNAs and lncRNAs using long RNA expression data. InMiR is a computational method that predicts the targets of intronic miRNAs based on the expression profiles of their host genes across a large number of datasets. InMiR can also predict which host genes have expression profiles that are good surrogates for those of their intronic miRNAs. Host genes that InMiR predicts are bad surrogates contain significantly more miRNA target sites in their 3 UTRs and are significantly more likely to have predicted Pol II-III promoters in their introns. We also develop BayMiR that scores miRNA-mRNA pairs based on the endogenous footprint of miRNAs on gene expression in a genome-wide scale. BayMiR provides an ``endogenous target repression" index, that identifies the contribution of each miRNA in repressing a target gene in presence of other targeting miRNAs. This thesis also addresses the interactions between miRNAs and lncRNAs. Our analysis on expression abundance of long RNA transcripts (mRNA and lncRNA) shows that the lncRNA target set of some miRNAs have relatively low abundance in the tissues that these miRNAs are highly active. We also found lncRNAs and mRNAs that shared many targeting miRNAs are significantly positively correlated, indicating that these set of highly expressed lncRNAs may act as miRNA sponges to promote mRNA regulation.

Page generated in 0.0636 seconds