475 research outputs found
Kolmogorov Complexity and Solovay Functions
No full textSolovay (1975) proved that there exists a computable upper bound~ of the prefix-free Kolmogorov complexity function~ such that for infinitely many~. In this paper, we consider the class of computable functions~ such that for all~ and for infinitely many~, which we call Solovay functions. We show that Solovay functions present interesting connections with randomness notions such as Martin-L\"of randomness and K-triviality
Foundations of Online Structure Theory II: The Operator Approach
No full textWe introduce a framework for online structure theory. Our approach
generalises notions arising independently in several areas of computability
theory and complexity theory. We suggest a unifying approach using operators
where we allow the input to be a countable object of an arbitrary complexity.
We give a new framework which (i) ties online algorithms with computable
analysis, (ii) shows how to use modifications of notions from computable
analysis, such as Weihrauch reducibility, to analyse finite but uniform
combinatorics, (iii) show how to finitize reverse mathematics to suggest a fine
structure of finite analogs of infinite combinatorial problems, and (iv) see
how similar ideas can be amalgamated from areas such as EX-learning, computable
analysis, distributed computing and the like. One of the key ideas is that
online algorithms can be viewed as a sub-area of computable analysis.
Conversely, we also get an enrichment of computable analysis from classical
online algorithms
Dr. Wade Downey - Faculty Author Interview
No full textDr. Wade Downey, Professor of Chemistry in the School of Arts and Sciences, and his student lab group study the ability of trimethylsilyl trifluoromethanesulfonate (TMSOTf) to mediate new reactivity or increase the efficiency of known reactions. The most likely downstream application of this new chemistry is in the fields of pharmaceuticals, pesticides, and herbicides. In 2018 he co-authored two articles, along with his students, in both the Journal of Organic Chemistry and Tetrahedron Letters
David Downey
No full textDave is an award winning safety leader and the founder of Downey Aviation Services.
Dave’s aerospace experience includes civil certification, flight operations and safety/risk management. He is a published author and international public speaker on aviation and leadership.
Mr. Downey most recent role was as President, North America, at Aerosafe Risk Management. Prior to that role he was a Vice President at Bell Helicopter where he was responsible for Systems Engineering, Engineering Operations, Flight Test Operations, Flight Safety, the Bell Organization Delegation Authorization and the Product Safety Board. He streamlined processes and developed leadership training.
Prior to joining Bell, Mr. Downey was a member of the FAA Senior Executive Service where he served as the Manager, FAA Rotorcraft Directorate in Fort Worth, Texas. He provided strategic direction on all aspects of rotorcraft and tilt-rotor policy/certification. In this position he was also responsible for all FAA experimental flight test policy, training and administration. He was a Team Leader on the FAA Safer Skies Commercial Aviation safety program. As Co-Chair of the International Helicopter Safety Team, Dave achieved a 33% reduction in the number of U. S. fatal helicopter accidents. He has FAA engineering and manufacturing experience with engines, propellers, APUs, UAVs and airplanes. He has also worked closely with the NTSB and international Aviation Authorities such as TCCA, EASA, CAAC and ICAO.
Dave began his career as a U. S. Army Pilot. He has military experience as an instructor pilot, instrument flight examiner, maintenance test pilot, and experimental test pilot. He served as an Exchange Officer to the United Kingdom as a Senior Test Pilot. His aviation experience includes over 4000 hours of fixed and rotary wing accident-free flying on 125 different models. He holds an FAA Airline Transport Pilot rating as well as: single/multi engine land/seaplane and helicopter commercial pilot, and CFI ground.
Dave graduated from the University of Tennessee Space Institute with an MS and earned his BS from Embry Riddle Aeronautical University. He also graduated from the US Navy Test Pilot School. Dave is the 2010 Society of Experimental Test Pilots Tony LaVier Flight Safety Award for life time achievement in Flight Safety.https://commons.erau.edu/lep-images/1000/thumbnail.jp
05301 Summary – Exact Algorithms and Fixed-Parameter Tractability
No full textSummary of the Dagstuhl Seminar held 24. July - 29. July 2005
05301 Abstracts Collection – Exact Algorithms and Fixed-Parameter Tractability
No full textFrom 24.07.05 to 29.07.05, the Dagstuhl Seminar 05301 ``Exact Algorithms and Fixed-Parameter Tractability'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl.
This is a collection of abstracts of the presentations given during the seminar
A Parameterized Complexity Tutorial
No full textAbstract. The article was prepared for the LATA 2012 conference where I will be presenting two one and half hour lecctures for a short tutorial on parameterized complexity. Much fuller accounts can be found in the books Downey-Fellows [DF98,DFta], Niedermeier [Nie06], Flum-Grohe [FG06], the two issues of the Computer Journal [DFL08] and the recent survey Downey-Thilikos [DTH11]
Contributions to Parameterized Complexity
No full textThis thesis is presented in two parts. In Part I we concentrate on algorithmic aspects of parameterized complexity. We explore ways in which the concepts and algorithmic techniques of parameterized complexity can be fruitfully brought to bear on a (classically) well-studied problem area, that of scheduling problems modelled on partial orderings. We develop efficient and constructive algorithms for parameterized versions of some classically intractable scheduling problems.
We demonstrate how different parameterizations can shatter a classical problem into both tractable and (likely) intractable versions in the parameterized setting; thus providing a roadmap to efficiently computable restrictions of the original problem.
We investigate the effects of using width metrics as restrictions on the input to online problems. The online nature of scheduling problems seems to be ubiquitous, and online situations often give rise to input patterns that seem to naturally conform to restricted width metrics. However, so far, these ideas from topological graph theory and parameterized complexity do not seem to have penetrated into the online algorithm community.
Some of the material that we present in Part I has been published in [52] and [77].
In Part II we are oriented more towards structural aspects of parameterized complexity. Parameterized complexity has, so far, been largely confined to consideration of computational problems as decision or search problems. We introduce a general framework in which one may consider parameterized counting problems, extending the framework developed by Downey and Fellows for decision problems.
As well as introducing basic definitions for tractability and the notion of a parameterized counting reduction, we also define a basic hardness class, #W[1], the parameterized analog of Valiant's class #P. We characterize #W[1] by means of a fundamental counting problem, #SHORT TURING MACHINE ACCEPTANCE, which we show to be complete for this class. We also determine #W[1]-completeness, or #W[l]-hardness, for several other parameterized counting problems.
Finally, we present a normalization theorem, reworked from the framework developed by Downey and Fellows for decision problems, characterizing the #W[t],(t є N). parameterized counting classes.
Some of the material that we present in Part II has been published in [78]
Lowness for bounded randomness
No full textAbstractIn [3], Brodhead, Downey and Ng introduced some new variations of the notions of being Martin-Löf random where the tests are all clopen sets. We explore the lowness notions associated with these randomness notions. While these bounded notions seem far from classical notions with infinite tests like Martin-Löf and Demuth randomness, the lowness notions associated with bounded randomness turn out to be intertwined with the lowness notions for these two concepts. In fact, in one case, we get a new and likely very useful characterization of K-triviality
Undecidability Results for low complexity degree structures (Extended Abstract)
No full textRod Downey , Victoria University of Wellington New Zealand Andr'e Nies y The University of Chicago Chicago Illinois 60637 USA Abstract We prove that the theory of EXPTIME degrees with respect to polynomial time Turing and many-one reducibility is undecidable. To do so we use a coding method based on ideal lattices of Boolean algebras which was introduced in [7]. The method can be applied in fact to all hyper-polynomial time classes. 1 Introduction If h is a time constructible function which dominates all polynomials, then, by the methods of the deterministic time hierarchy theorem, DT IME(h) properly contains P. Therefore, a polynomial time reducibility like polynomial time many--one or Turing reducibility induces a nontrivial degree structure on DT IME(h). This degree structure is an uppersemilattice with least element 0. Moreover, by the methods of Ladner ([6], also see [4], Chapter I.7), this degree structure is dense. This was so far the only fact known to hold in general for..
- …
