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 41 for “"Worst-case complexity"”.
-
Fast exact algorithms for optimization problems in resource allocation and switched linear systems
… divide-and-conquer algorithm and the worst-case complexity is usually not achieved. Numerical experiments demonstrate that our algorithm significantly outperforms a state-of-the-art optimization solver and the performance of our algorithm is competitive compared to the algorithm with …
-
Proofdoors and efficiency of CDCL solvers
This thesis studies the gap between the worst-case complexity of SAT and the strong practical performance of CDCL solvers. It builds on the notion of proofdoors, a structural decomposition of CNF formulas into sequential components connected by interpolants. We show that formulas admitting small …
-
Saturation−Based Decision Procedures for Extensions of the Guarded Fragment
… used tableau procedures, such as optimal worst-case complexity and direct correctness proofs
-
Information, complexity and structure in convex optimization
… algorithms. Classical theory of oracle complexity, first proposed by Nemirovski and Yudin in 1983, successfully established the worst-case behavior of methods based on local oracles (a generalization of first-order oracle for smooth functions) for nonsmooth convex minimization, both in …
-
Robot path planning with a moving goal.
… previous planning data to update the path in the case where the target moves. The algorithm in this thesis addresses the need for a quick path-planner that can be used in an environment where the target is moving. The algorithm does this by sacrificing optimality in order to reduce the complexity …
-
Computational convex analysis using parametric quadratic programming
… conjugates. We provide a complete space and time worst-case complexity analysis and show that for bivariate functions, the algorithm matches the performance of [Computing the Conjugate of Convex Piecewise Linear-Quadratic Bivariate Functions, Bryan Gardiner and Yves Lucet, Mathematical Programming …
-
Resource allocation problems in MIMO-OFDM systems
… for optimal power allocation is devised. The worst case complexity of this algorithm is O(n²) per iteration. Finally in numerical studies we show the user power allocations and spectral efficiency of the algorithms.
-
Truncation maps and geometry of deep learning
… training and test data, rather than on worst-case complexity over the full hypothesis class. Overall, the dissertation develops geometric tools for understanding how deep neural networks represent data, evolve under training, and generalize beyond the training set.
-
An investigation on Integer Factorization applied to Public Key Cryptography
… its factors is commonly believed to be hard (worst-case complexity). In this thesis, after a brief explaination of the developments on integer factorization and a description of the General Number Field Sieve (GNFS), we will present different strategies to face this well-known problem of …
-
A Computational Study of Problems in Sports
… The second problem addressed is determining the complexity, either worst-case theoretical or practical, of manipulation strategies in sports tournaments. The two most common types of competitions, cups and round robins, are considered and it is shown that there exists a number of polynomial time …
-
Joint resource allocation and routing in wireless networks via convex approximation techniques
… convex approximation approach, in which case we utilize the ADMoM method towards distributed implementation, and the iteratively re-weighted Minimum Mean Square Error approach. Our simulation results show that the proposed algorithms offer excellent throughput performance at low …
-
Selection of flip-flops for partial scan design
… in a given circuit, but it has exponential worst case complexity. The heuristic algorithm, on the other hand, obtains a near optimal solution in shorter time. ETA provides a spectrum of accurate fault efficiency and/or fault coverage so that the designer can choose an affordable option. The …
-
Consequence-based reasoning for SRIQ ontologies
… consequence-based algorithms, namely optimal worst-case complexity, one-pass classification, and pay-as-you-go behaviour.</p> <p>To evaluate the practicability of our calculus, we implemented it in <em>Sequoia</em>—a new DL reasoning system. Empirical results show substantial robustness …
-
Quantum algorithms for linear and nonlinear differential equations
… with sufficiently weak dissipation have worst-case complexity exponential in time, giving an almost tight classification of the quantum complexity of simulating nonlinear dynamics. Overall, utilizing advanced linear algebra techniques and nonlinear analysis, I attempt to build a bridge …
-
Exact Methods In Fractional Combinatorial Optimization
… while for the other one only the theoretical complexity issues are addressed. The dissertation emphasizes developing solution methodologies for the considered family of fractional programs. The main contributions include: (i) worst-case complexity results for the MMRP and MMRC problems; (ii) …
-
Structure and complexity in non-convex and non-smooth optimization
Complexity theory drives much of modern optimization, allowing a fair comparison between competing numerical methods. The subject broadly seeks to both develop efficient algorithms and establish limitations on efficiencies of any algorithm for the problem class. Classical complexity theory based on …
-
Automated Tracking of Mouse Embryogenesis from Large-scale Fluorescence Microscopy Data
… scale to the data with such large size and high complexity. For those purposely designed for embryo data analysis, the accuracy is heavily sacrificed. Here, we present a new computational framework for the mouse embryo data analysis with high accuracy and efficiency. Our framework detects and …
-
Efficient Evaluation of Set Expressions
… and the sizes of the sets, we investigate the worst-case complexity of evaluating the expression in terms of the sizes of the sets. We prove lower bounds and provide algorithms with the matching running time up to a constant factor. We then refine the problem further and design an algorithm …
-
A graph based approach for formal verification of Galois field multipliers
… methods increase exponentially with the size and complexity of circuits. Formal verification has the potential to improve the verification process by providing better than exponential complexity for some systems. Conventional formal verification methods do not perform well on cryptography circuits …
-
Exploring Finite-Word Automata for Reactive Synthesis
… not only because of the problem's 2EXPTIME worst-case complexity, but also because algorithms often rely on manipulation of automata over infinite words, for which there are no known efficient algorithms. The goal of this thesis is to take steps towards bringing reactive synthesis to the …
Page 1 of 3