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 30 for “"sublinear-time"”.

  1. Computing (1+ϵ)-Approximate Degeneracy in Sublinear Time

    … the degeneracy problem which runs in O(n log n) time on a graph with n nodes, sublinear in the input size for dense graphs, by sampling a small number of neighbours adjacent to high degree nodes. Our algorithm can also be extended to an O(n log n) time solution to the k-core decomposition …

    uvic Repository record for Computing (1+ϵ)-Approximate Degeneracy in Sublinear Time (opens in a new tab)

  2. Sublinear Time Evaluation of Logically Defined Queries on Databases of Bounded Degree

    … as 'efficient' (i.e. run in polynomial time) become impractical. This motivates the study of algorithms that run in sublinear time. To achieve sublinear time, it is unavoidable that we must sacrifice some accuracy (since we cannot read the whole input), but in view of many practical …

    whiterose Download PDF for Sublinear Time Evaluation of Logically Defined Queries on Databases of Bounded Degree (opens in a new tab)

  3. Improved algorithms and new models in property testing

    We study sublinear-time algorithms for testing fundamental properties of functions and graphs. Sublinear-time algorithms run in time sublinear in the input size and are especially useful for processing massive datasets. We investigate variants of the property testing model, which was introduced by …

    bu Repository record for Improved algorithms and new models in property testing (opens in a new tab)

  4. Robust and Efficient Algorithms for Protein 3-D Structure Alignment and Genome Sequence Comparison

    … of points arose and its connection to the sublinear time computation is discussed. The diameter calculation of a 3-D sequence is approximated by a series of sublinear time deterministic, zero-error and bounded-error randomized algorithms and we have obtained a series of separations about …

    uno Repository record for Robust and Efficient Algorithms for Protein 3-D Structure Alignment and Genome Sequence Comparison (opens in a new tab)

  5. Sublinear Algorithms for Statistical, Markov Chain, and Binpacking Problems

    … of data. We give new algorithms which use time and communication resources that are sublinear in the problem size for problems in various domains including statistics and combinatorics. We first consider properties of random variables. We begin with the problem of distinguishing whether two …

    cornell Repository record for Sublinear Algorithms for Statistical, Markov Chain, and Binpacking Problems (opens in a new tab)

  6. Parallel algorithms for free and associative-commutative unification

    … for systems using structure sharing. Apart from time and space savings, its use allows subterms to be tested for equality in constant time. The use of compact terms greatly simplifies free term matching and gives rise to a linear-time algorithm with lower processing overheads than the …

    oxford Repository record for Parallel algorithms for free and associative-commutative unification (opens in a new tab)

  7. FAST AND MEMORY EFFICIENT ALGORITHMS FOR STRUCTURED MATRIX SPECTRUM APPROXIMATION

    … scheme that can be implemented in linear time. In the second part, we give the first truly sublinear time algorithm to approximate the spectral density of the (normalized) adjacency matrix of an undirected, unweighted graph in earth-mover distance. In addition to our sublinear time result, …

    jhu Repository record for FAST AND MEMORY EFFICIENT ALGORITHMS FOR STRUCTURED MATRIX SPECTRUM APPROXIMATION (opens in a new tab)

  8. Modern Large-Scale Algorithms for Classical Graph Problems

    … computation that only allow the algorithm to use sublinear resources (such as time, space, or communication). Examples include (i) massively parallel computation (à la MapReduce) algorithms where the workload is distributed among several machines each with sublinear space/communication, (ii) …

    maryland Repository record for Modern Large-Scale Algorithms for Classical Graph Problems (opens in a new tab)

  9. Analyzing massive datasets with missing entries: models and algorithms

    … model, one of the most widely studied models of sublinear-time algorithms, to account for the presence of adversarially erased function values. We design efficient erasure-resilient property testing algorithms for several fundamental properties of real-valued functions such as monotonicity, …

    bu Repository record for Analyzing massive datasets with missing entries: models and algorithms (opens in a new tab)

  10. Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation

    … also explores other modern models, including sublinear-time, fully dynamic, and oracle-based models. The first part of the thesis develops space-optimal algorithms for fundamental graph problems in the streaming setting. We study approximate minimum cut, k-vertex connectivity, maximum …

    waterloo Repository record for Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation (opens in a new tab)

  11. Sub-linear sparse fourier transform algorithm

    … the Fast Fourier Transform (FFT), which has runtime O(N log N) for an input vector with length N. However, with the increasing size of data set, the FFT is no longer fast enough and often becomes the major computational bottleneck in many applications. The Sparse Fourier Transform (SFT) tries to …

    msu

  12. Formal verification of biologically inspired computing models

    … hard problems in polynomial - often linear or sublinear - time. Similar to other membrane computing models, cP systems work in an ideal way, having unlimited space and computing power. This thesis discusses the formal verification of cP systems. cP systems support labelled multiset-based terms …

    auckland-ms Repository record for Formal verification of biologically inspired computing models (opens in a new tab)

  13. Provably efficient methods for large-scale learning

    … sparse quadratic regression with sub-quadratic time complexity and near-optimal sample complexity. We then move to online learning problems. In Chapter 3, we identify a weak assumption and theoretically prove that the standard UCB algorithm efficiently learns from inconsistent human preferences …

    texas Repository record for Provably efficient methods for large-scale learning (opens in a new tab)

  14. Data Structures and Protocols for Scalability and Security of Distributed Consensus

    … maintainable (can update all proofs in sublinear time) and aggregatable (can combine multiple individual proofs into a single succinct proof). Hyperproofs also incentivize proof computation through a new property called unstealability, which allows a prover to cryptographically bind the …

    maryland Repository record for Data Structures and Protocols for Scalability and Security of Distributed Consensus (opens in a new tab)

  15. Sparse harmonic transforms

    … ideas in [1] and [2]. Furthermore, we develop sublinear-time compressive sensing methods to approximate the multivariate functions by the expansion of a few bounded orthonormal product (BOP) bases which include tensorized Fourier basis functions. These new methods are obtained from CoSaMP by …

    msu Repository record for Sparse harmonic transforms (opens in a new tab)

  16. On the Implementation of Purely Functional Data Structures for the Linearisation case of Dynamic Trees

    … for non persistent structures providing O(log n) time for update and lookup operations as shown in theory and practice by Werneck. However, there are two gaps in current theory. First, how the most common dynamic tree operations (link and cut) are computed over a purely functional data structure …

    whiterose Download PDF for On the Implementation of Purely Functional Data Structures for the Linearisation case of Dynamic Trees (opens in a new tab)

  17. Tractable relaxations and efficient algorithmic techniques for large-scale optimization

    … exact guarantees on solution quality, achieve sublinear time behavior, and through extensive simulations, show considerable improvement over the state-of-the-art deterministic FOMs. In the last part, we examine a general sparse estimation problem -estimating a block sparse linear transform of a …

    gatech Repository record for Tractable relaxations and efficient algorithmic techniques for large-scale optimization (opens in a new tab)

  18. Atomic -Scale Statistical Models of Semiconductor Device *Reliability

    … bond energies as the physical origin for the sublinear time dependence of the generation of silicon-silicon dioxide interface traps under hot electron stress. We demonstrate the consequences of this idea for the reliability of MOSFET devices under hot electron stress, and point out that one …

    uiuc Repository record for Atomic -Scale Statistical Models of Semiconductor Device *Reliability (opens in a new tab)

  19. Matrix theory : optimization, concentration, and algorithms

    … and doing so often yields the best-known runtime. We present an algorithm that runs in the current matrix multiplication time, which breaks a thirty-year-old barrier. Furthermore, our technique can be generalized to speed up a large family of convex optimization problems, i.e., empirical risk …

    texas Repository record for Matrix theory : optimization, concentration, and algorithms (opens in a new tab)

  20. Space-Efficient Data Structures for Information Retrieval

    … compressed text that support searching in sublinear time. In order to build our indexes, we present new results on representing binary relations in a space-efficient manner, and construction algorithms that use little space to achieve their goal. These two results have a wide range of …

    waterloo Repository record for Space-Efficient Data Structures for Information Retrieval (opens in a new tab)

Page 1 of 2