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"”.
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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, …
-
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 …