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

  1. 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 …

    umn Repository record for Fast exact algorithms for optimization problems in resource allocation and switched linear systems (opens in a new tab)

  2. 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 …

    gatech Repository record for Proofdoors and efficiency of CDCL solvers (opens in a new tab)

  3. Saturation−Based Decision Procedures for Extensions of the Guarded Fragment

    … used tableau procedures, such as optimal worst-case complexity and direct correctness proofs

    oxford Restricted access

  4. 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 …

    gatech Repository record for Information, complexity and structure in convex optimization (opens in a new tab)

  5. 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 …

    baylor Repository record for Robot path planning with a moving goal. (opens in a new tab)

  6. 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 …

    ubc Repository record for Computational convex analysis using parametric quadratic programming (opens in a new tab) Download PDF for Computational convex analysis using parametric quadratic programming (opens in a new tab)

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

    ubc Repository record for Resource allocation problems in MIMO-OFDM systems (opens in a new tab) Download PDF for Resource allocation problems in MIMO-OFDM systems (opens in a new tab)

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

    texas Repository record for Truncation maps and geometry of deep learning (opens in a new tab)

  9. 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 …

    trento Repository record for An investigation on Integer Factorization applied to Public Key Cryptography (opens in a new tab) Restricted access

  10. 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 …

    waterloo Repository record for A Computational Study of Problems in Sports (opens in a new tab)

  11. 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 …

    greece Repository record for Joint resource allocation and routing in wireless networks via convex approximation techniques (opens in a new tab)

  12. 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 …

    vt Repository record for Selection of flip-flops for partial scan design (opens in a new tab)

  13. 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 …

    oxford Repository record for Consequence-based reasoning for SRIQ ontologies (opens in a new tab)

  14. 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 …

    maryland Repository record for Quantum algorithms for linear and nonlinear differential equations (opens in a new tab)

  15. 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) …

    tamu Repository record for Exact Methods In Fractional Combinatorial Optimization (opens in a new tab)

  16. 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 …

    washington Repository record for Structure and complexity in non-convex and non-smooth optimization (opens in a new tab)

  17. 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 …

    vt Repository record for Automated Tracking of Mouse Embryogenesis from Large-scale Fluorescence Microscopy Data (opens in a new tab)

  18. 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 …

    waterloo Repository record for Efficient Evaluation of Set Expressions (opens in a new tab)

  19. 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 …

    waterloo Repository record for A graph based approach for formal verification of Galois field multipliers (opens in a new tab)

  20. 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 …

    rice Repository record for Exploring Finite-Word Automata for Reactive Synthesis (opens in a new tab)

Page 1 of 3