Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 157 for “"space complexity"”.

  1. On the Space Complexity of Colourless Tasks

    In this thesis, we prove lower bounds on the number of registers needed to solve colourless tasks in asynchronous shared memory systems. Many fundamental synchronization tasks, such as consensus, k-set agreement, and epsilon-approximate agreement, are colourless. We show that it is possible to …

    toronto-retro Repository record for On the Space Complexity of Colourless Tasks (opens in a new tab)

  2. Time and space complexity of rule-based graph programs

    This thesis concerns the time and space efficiency of programs in GP 2, a rule-based graph transformation language that facilitates formal program analysis. Such programs are a sequence of control structures in which rules are called. A rule describes how part of a host graph is changed to another …

    whiterose Download PDF for Time and space complexity of rule-based graph programs (opens in a new tab)

  3. The Space Complexity of Asynchronous Algorithms from Bounded Size Base Objects

    … objects also gives us more power to prove new space complexity lower bounds. We devise a new technique for obtaining space complexity lower bounds for obstruction-free algorithms that use bounded size base objects. First, we consider obstruction-free implementations of scannable objects, which …

    toronto-retro Repository record for The Space Complexity of Asynchronous Algorithms from Bounded Size Base Objects (opens in a new tab)

  4. The Space Complexity of Distributed Tasks in the Shared Memory Model

    In this thesis, I study the space complexity of the implementation of test-and-set and renaming problems from atomic multi-reader/multi-writer registers in distributed synchronous systems with n processes. Previously, Giakkoupis and Woelfel as well as Styer and Peterson showed that at least …

    calgary Repository record for The Space Complexity of Distributed Tasks in the Shared Memory Model (opens in a new tab)

  5. Channel-based Physical Layer Authentication

    … some existing schemes at a cost of extra time complexity and space complexity due to the training stage. To reduce the space complexity and time complexity during the training stage, LFDA based authentication scheme is proposed. In LFDA based scheme, a linear combination of the channel features …

    waterloo Repository record for Channel-based Physical Layer Authentication (opens in a new tab)

  6. Supervisory Control Using DEVS with Approximate Method and Hybrid Layer

    … restricted to robotics due to the issue of state space explosion as model size increases. Reduction in the state space complexity can expand the practicality of the model. We use the Discrete Event System Specifications (DEVS) formalism to implement supervisory control with an approximate method …

    carleton Repository record for Supervisory Control Using DEVS with Approximate Method and Hybrid Layer (opens in a new tab)

  7. Approximation of General CPTs with NIN-AND Tree Models

    … by conditional probability tables (CPTs). The space complexity of BNs is exponential on the number of parents per variable, which limits the effectiveness of knowledge acquisition and inference. Non-impeding noisy-AND tree (NAT) models give a highly expressive approximate representation of BNs. …

    guelph Repository record for Approximation of General CPTs with NIN-AND Tree Models (opens in a new tab)

  8. Models of 2D-scene complexity : a look at the intrinsic complexity of scenes

    The worst-case time and space complexity of many algorithms in computational geometry is high when expressed as a function of the input size. This can make algorithms seem inefficient in general. Usually, however, the algorithm will not run with identical times on every input of a given size. …

    ubc Repository record for Models of 2D-scene complexity : a look at the intrinsic complexity of scenes (opens in a new tab) Download PDF for Models of 2D-scene complexity : a look at the intrinsic complexity of scenes (opens in a new tab)

  9. Efficient random projection trees for nearest neighbor search and related problems

    … recent years, a solution better than linear time complexity is desirable. Locality sensitivity hashing (LSH) and random projection trees (RPT) are two popular methods to solve NNS problem in sublinear time. Earlier works have demonstrated that RPT has superior performance compared to LSH. However, …

    wichita-thes Repository record for Efficient random projection trees for nearest neighbor search and related problems (opens in a new tab)

  10. Efficient Community Search on Large Bipartite Graphs

    … Pareto-optimal (α, β)-communities with the time complexity of O(p · m) where p is the number of resulting communities, and m is the number of edges in the bipartite graph G. To support efficient query processing over large graphs, we also develop index-based approaches. A complete index is …

    unsw Repository record for Efficient Community Search on Large Bipartite Graphs (opens in a new tab)

  11. Pessimistic Bayesianism for conservative optimization and imitation

    … modelling that allows for log-linear time complexity and linear space complexity, instead of a naïve cubic time complexity and quadratic space complexity. This is not the first Gaussian process with this time complexity—inducing points methods have linear complexity—but we do outperform …

    oxford Repository record for Pessimistic Bayesianism for conservative optimization and imitation (opens in a new tab)

  12. Group Mutual Exclusion in Linear Time and Space

    … Served. Our algorithm has [theta] (N) shared space complexity and [omicron] (N)RMR (Remote Memory Reference) complexity. Our algorithm is developed by generalizing the well-known Lamport's Bakery Algorithm for the classical mutual exclusion problem, while preserving its simplicity and …

    ecu Repository record for Group Mutual Exclusion in Linear Time and Space (opens in a new tab)

  13. Shapes and implementations in three-dimensional geometry

    … is in its abstract form a finite point set in space, and it is often useful or required to compute what one might call the ""shape"" of the set. For that purpose, this thesis deals with the formal notion of the family of alpha shapes of a finite point set in three-dimensional space. Each shape …

    uiuc Repository record for Shapes and implementations in three-dimensional geometry (opens in a new tab)

  14. Techniques for analyzing the computational power of constant-depth circuits and space-bounded computation

    The subject of computational complexity theory is to analyze the difficulty of solving computational problems within different models of computation. Proving lower bounds is easier in less powerful models and proving upper bounds is easier in the more powerful models. This dissertation studies …

    texas Repository record for Techniques for analyzing the computational power of constant-depth circuits and space-bounded computation (opens in a new tab)

  15. Large-scale methods in computational genomics

    … through the development of faster algorithms, space-efficient methods, and high-performance parallel computing techniques for some key problems in computational genomics;The first problem addressed is the clustering of DNA sequences based on a measure of sequence similarity. Our clustering …

    iastate Repository record for Large-scale methods in computational genomics (opens in a new tab)

  16. Unambiguous logarithmic space bounded computations

    Space complexity investigates the power and limitations of a computational model (e.g. a Turing machine) which has a limited amount of workspace to perform its computation. Particularly interesting is the case when the space is only logarithmic in the input size. Unambiguous computation is a …

    nebraska Repository record for Unambiguous logarithmic space bounded computations (opens in a new tab)

  17. Computer vision using shape spaces / Burzin Bhavnagri.

    … This leads to an algorithm with linear time and space complexity to generate a collection of feature points with attributes in cyclically ordered groups. Two approaches to rejecting false hypotheses of correspondence were developed: an error minimising approach and an approach based on formal …

    adelaide Repository record for Computer vision using shape spaces / Burzin Bhavnagri. (opens in a new tab)

  18. Combinatorial Optimization On Massive Datasets: Streaming, Distributed, And Massively Parallel Computation

    … in this part include a tight bound on the space complexity of the matching problem in dynamic streams, a unifying framework for achieving algorithms that improve the state-of-the-art for matching and vertex cover problems in all the mentioned models, and the first massively parallel …

    penn Repository record for Combinatorial Optimization On Massive Datasets: Streaming, Distributed, And Massively Parallel Computation (opens in a new tab)

  19. Filling contours on the linear quadtree domain by insertion and traversal

    … existing LQT filling algorithms both in time and space complexity. The technique avoids explicit sorting of the input pixels or output cells by location code, and no condensation of cells is required. Traversing the regular quadtree in preorder generates the sorted output cells as an LQT.

    ubc Repository record for Filling contours on the linear quadtree domain by insertion and traversal (opens in a new tab) Download PDF for Filling contours on the linear quadtree domain by insertion and traversal (opens in a new tab)

Page 1 of 8