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"”.
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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, …
-
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) …
-
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, …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
Page 1 of 2