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 10 of 10 for “"Sublinear algorithms"”.

  1. Complexity of Sublinear Algorithms for Convexity in Higher Dimensions

    Convexity plays a prominent role in both mathematics and computer science. It is defined for sets and functions, and many related problems can be solved efficiently if the set/function is convex. In this thesis, we focus on three problems related to convexity where we don't have that guarantee. The …

    waterloo Repository record for Complexity of Sublinear Algorithms for Convexity in Higher Dimensions (opens in a new tab)

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

    We consider the problem of how to construct algorithms which deal efficiently with large amounts 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 …

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

  3. Sublinear Algorithm And Lower Bound For Combinatorial Problems

    … a single computer. In these cases, the classical algorithms may no longer be feasible options, even when they run in linear time and linear space, as the input size is too large. In this thesis, we study various combinatorial problems in different computation models that process large input sizes …

    penn Repository record for Sublinear Algorithm And Lower Bound For Combinatorial Problems (opens in a new tab)

  4. SUBLINEAR GRAPH SPARSIFICATION WITH APPLICATIONS TO CUTS, MATCHINGS, AND FLOWS

    … there has been growing interest in developing algorithms that are highly resource-efficient in terms of time, space, and communication. Although some algorithms in the existing literature are deemed efficient in the conventional sense that they require polynomial time and space in the input …

    penn Repository record for SUBLINEAR GRAPH SPARSIFICATION WITH APPLICATIONS TO CUTS, MATCHINGS, AND FLOWS (opens in a new tab)

  5. Testing, Learning, Sampling, Sketching

    We study several problems about sublinear algorithms, presented in two parts. Part I: Property testing and learning. There are two main goals of research in property testing and learning theory. The first is to understand the relationship between testing and learning, and the second is to develop …

    waterloo Repository record for Testing, Learning, Sampling, Sketching (opens in a new tab)

  6. Novel Fast Algorithms For Low Rank Matrix Approximation

    … l log n) m ) operations. We also prove that our sublinear cost variants of a popular subspace sampling algorithm output accurate low rank approximation (hereafter LRA) of a large class of input. Finally, we introduce new sublinear algorithms for the CUR LRA matrix factorization which consists of …

    cuny-grad Repository record for Novel Fast Algorithms For Low Rank Matrix Approximation (opens in a new tab)

  7. Lower bounds for sparse recovery problems

    … used in areas like image acquisition, streaming algorithms, genetic testing, and, more recently, for image recovery tasks. Over the last decade many techniques have been developed for sparse recovery under various guarantees. We develop new lower bound techniques and show the tightness of …

    texas Repository record for Lower bounds for sparse recovery problems (opens in a new tab)

  8. 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)

  9. Analytic Property Testing: Directed Isoperimetry and Monotonicity

    … is a computational paradigm that aims to design algorithms for extremely fast decision-making about massive inputs. Property testing has been studied for nearly three decades, primarily with a focus on testing properties about discrete objects such as Boolean functions and graphs. In this thesis, …

    waterloo Repository record for Analytic Property Testing: Directed Isoperimetry and Monotonicity (opens in a new tab)

  10. Halfway to Halfspace Testing

    In this thesis I study the problem of testing halfspaces under arbitrary probability distributions, using only random samples. A halfspace, or linear threshold function, is a boolean function f : Rⁿ → {±1} defined as the sign of a linear function; that is, f(x) = sign(Σᵢ wᵢxᵢ - θ) where we refer to …

    waterloo Repository record for Halfway to Halfspace Testing (opens in a new tab)