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 223 for “"Sublinear"”.
-
Matrix Low Rank Approximation at Sublinear Cost
A matrix algorithm runs at sublinear cost if the number of arithmetic operations involved is far fewer than the number of entries of the input matrix. Such algorithms are especially crucial for applications in the field of Big Data, where input matrices are so immense that one can only store a …
-
Computing (1+ϵ)-Approximate Degeneracy in Sublinear Time
… 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 problem. This improves upon the …
-
Sublinear rigidity of lattices in semisimple lie groups
… be such a group. The first result is that if the sublinear neighbourhood of a discrete subgroup of G contains a lattice, then it is itslef a lattice. In case the group G does not admit real rank 1 factors, I prove that the classses of uniform and non-uniform lattices of G are SBE-complete, …
-
Sublinear Algorithm And Lower Bound For Combinatorial Problems
… problems, which give frameworks for achieving sublinear algorithms of these problems in different models. We also show that the sublinear algorithms for (∆ + 1)-coloring problem are tight. We then consider the graph sparsification problem, which is an important technique for designing sublinear …
-
Boundary value problems of second order sublinear ODEs
This Thesis studies second order sublinear ODEs with keen interest in the sublinear case of the generalized Emden-Fowler equation with nonnegative boundary data. We proved existence and uniqueness results for positive solutions. Our results generalize some earlier results in the literature on the …
-
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
… 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 distributions over the same domain are …
-
SUBLINEAR GRAPH SPARSIFICATION WITH APPLICATIONS TO CUTS, MATCHINGS, AND FLOWS
… been an increasingly important topic to design sublinear algorithms, whose resource consumption is smaller than the size of the data. In this thesis, we focus on developing sublinear algorithms for datasets with graph structures, such as social networks, biological networks and Web networks, …
-
A sublinear version of the Schur test and weighted norm inequalities /
In this dissertation, we provide results which characterize when a class of partial differential equations can be solved. These partial differential equations arise in the study of the Porous Media Equation, which can model nonlinear heat transfer, groundwater flow, and population dynamics. The …
-
Sublinear Time Evaluation of Logically Defined Queries on Databases of Bounded Degree
… 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 applications it is crucial that we provide guarantees on the accuracy of the …
-
A CHARACTERIZATION OF PROPER MINIMAL POINTS AS SOLUTIONS OF SUBLINEAR OPTIMIZATION PROBLEMS
We consider the problem of finding the set of proper minimal (proper efficient, proper Pareto optimal) points of a given subset of an infinite dimensional locally convex space with partial order induced by a convex cone. Different definitions for a proper minimal point of a set, not necessarily …
-
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) …
-
Nonlinear semimartingales and Markov processes
… dynamic programming principle for the associated sublinear expectation and we link the corresponding value function to a variational form of a nonlinear path-dependent partial differential equation. Further, we establish conditions that allow us to identify the value function as the unique …
-
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 …
-
Identification of Urban Scaling Behavior for Transportation Mode Share
… then characterizes the scaling regime, either sublinear or super-linear where super-linear scaling reflects increasing returns with an increase in population while sublinear scaling represents economies of scale. This analysis approach has previously not been applied to the transportation …
-
Probabilistic design in the operation of service systems
… descent in Euclidean space. We establish sublinear static regret under geodesic convexity and sublinear dynamic regret with bounded variation. When decisions are probability densities, we provide conditions ensuring the algorithm remains within the space of densities while maintaining …
-
Thresholded linear bandits
… bandits, and learning halfspaces. To achieve sublinear regret in the presence of exponentially many arms, one method is to exploit the structure of the reward function. However, the presence of an unknown threshold component makes previously known algorithms for structured bandits unsuitable. …
-
Lévy-Type Processes under Uncertainty and Related Nonlocal Equations
… mathematical finance, advances in the theory of sublinear expectations (also referred to as coherent risk measures) lay the theoretical foundation for modern approaches to evaluations under the presence of Knightian uncertainty. In this book, we introduce and study a large class of jump-type …
Page 1 of 12