1,966 research outputs found
Better Complexity Bounds for Cost Register Automata
No full textCost register automata (CRAs) are one-way finite automata whose transitions have the side-effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the tropical semiring can simulate polynomial time computation, proving along the way that a naturally dened width-k circuit value problem over the tropical semiring is P-complete. Then the copyless variant of the CRA, requiring that semiring operations be applied to distinct registers, is shown no more powerful than NC1 when the semiring is the integers, or strings with operations max and concat. This relates questions left open in recent work on the complexity of CRA-computable functions to long-standing class separation conjectures in complexity theory, such as NC versus P and NC1 versus GapNC1.Paper presented at the 42nd International Symposium on Mathematical Foundations of Computer Science, August 21-25, 2017, Aalborg, Denmark. This is the Author’s Original, a longer and more complete version of the paper published in: Larsen, K.G., Bodlaender, H.L., & Raskin, J.-F. (Eds.). (2017). Proceedings from 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. (Leibniz International Proceedings in Informatics (LIPIcs)). DOI: 10.4230/LIPIcs.MFCS.2017.24.Peer reviewed
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
No full textThe Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) within a factor of n1−o(1) is indeed NP-intermediate. To the best of our knowledge, these problems are the first natural NP-intermediate problems under the existence of an arbitrary one-way function.
We also prove that MKTP is hard for the complexity class DET under non-uniform NC0 reductions.
This is surprising, since prior work on MCSP and MKTP had highlighted weaknesses of “local” reductions such as NC0-many-one reductions. We exploit this local reduction to obtain several new consequences:
* MKTP is not in AC0[p].
* Circuit size lower bounds are equivalent to hardness of a relativized version MKTPA of MKTP under a class of uniform AC0 reductions, for a large class of sets A.
* Hardness of MCSPA implies hardness of MKTPA for a wide class of sets A. This is the first result directly relating the complexity of MCSPA and MKTPA, for any A.Paper presented at the 42nd International Symposium on Mathematical Foundations of Computer Science, August 21-25, 2017, Aalborg, Denmark. This is the Author’s Original, a longer and more complete version of the paper published in: Larsen, K.G., Bodlaender, H.L., & Raskin, J.-F. (Eds.). (2017). Proceedings from 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. (Leibniz International Proceedings in Informatics (LIPIcs)). DOI: 10.4230/LIPIcs.MFCS.2017.54.Peer reviewed
First in the Nation in Education : Final Report,1984.
No full textThis report is one step in an ongoing process of change and is a plea for commitment for high standards in education in Iowa. Contains the final reports of the six subcommittees as adopted by the Excellence in Education Task Force, and the five recommendations made by the Task Force
Evaluating Research in Context: Pilot Study at Faculty of Architecture TU Delft
No full textThe vice chancellor of Delft University of Technology, Prof.dr.ir. J. Fokkema, introduced a pilot Evaluating Research in Context (ERiC) at the Faculty of Architecture. The Faculty of Architecture perceives a serious confl ict between the demands and criteria in evaluation procedures and the ambition to be relevant for the practice of architecture, planning and building. The goal of this ERiC pilot is to develop an evaluation method that judges research in the Faculty of Architecture on all its merits and takes into account the specifi c characteristics of architecture research. A second goal is the improvement of the evaluation of research contributions to society. This report presents the full results of this project and gives recommendations how to use these results in an evaluation according to the Standard Evaluation Protocol 2009-2015.Architectur
Perceptions college-bound seniors at Campbellsport high school have of technology education classes and factors influencing participation in those classes
No full textIncludes bibliographical references
Vitalistic information systems in the South African public health system : a transactional analysis perspective
No full textIncludes bibliographical references
Report of work on ankylosing spondylitics in Hong Kong, 1982-1985
No full textpublished_or_final_versionI Foreword M.B. Lee Lee, M. B.Preface E. Ho Ho, E.Manuscript IIID Had Been Published in the Journal of the Hong Kong Psychiatric AssociationManuscripts IIA, IIB, IID Had Been Published/accepted For Publication in the Journal of Western Pacific Orthopaedic AssociationManuscript IIG (ii) Had Been Accepted For Publication in SpinePermission Had Been Obtained From the Publishers to Include These Manuscripts in This ReportII Medical and Surgical AspectsIII Paramedical Management ReviewIV The Ankylosing Spondylitis PHAB Club in Hong Kong M. B. Lee, E. Ho Lee, M. B. Ho, E. 115V The Future of Ankylosing Spondylitics in Hong Kong E. Ho Ho, E. 117A Clinical Review of 100 Cases of Ankylosing Spondylitics in Hong Kong Chinese E. Ho, L.C.S. Hsu, S.P. Chow, J.C.Y. Leong Ho, E. Hsu, L. C. S. Chow, S. P. Leong, J. C. Y. 1B Hla B27 Testing in Hong Kong Chinese E. Ho, S.C.F. Yuen, L.C.S. Hsu, S.P. Chow, J.C.Y. Leong Ho, E. Yuen, S. C. F. Hsu, L. C. S. CHOW. S. P. Leong, J. C. Y. 7C Total Hip Arthroplasty in Ankylosing Spondylitis - a Review of 40 Cases E. Ho, D. Fang, L.C.S. Hsu, J.C.Y. Leong Ho, E. Fang, D. Hsu, L. C. S. Leong, J. C. Y. 11D Radiological Study of the Ossification Pattern in the Spine Affected By Ankylosing Spondylitis E. Ho, F. L. Chan, L.C.S. Hsu, J.C.Y. Leong, A.C.M.C. Yau Ho, E. Chan, F. L. Hsu, L. C. S. Leong, J. C. Y. Yau, A. C. M. C. 19E Radiological Study of Spinal Pseudoarthrosis in Ankylosing Spondylitis F. L. Chan, E. Ho, L.C.S. Hsu, D. Fang, J.C.Y. Leong Chan, F. L. Ho, E. Hsu, L. C. S. Fang, D. Leong, J. C. Y. 23F Family Screening in Ankylosing Spondylitis in Hong Kong Chinese E. Ho Ho, E. 35G Neurological Complications in Ankylosing Spondylitis 37A Occupational Therapy in Ankylosing Spondylitics K. Chan, E. Ho Chan, K. Ho, E. 47B Physiotherapy in Ankylosing Spondylitics D. Wong, J.M. Bourne, E. Ho Wong, D. Bourne, J. M. Ho, E. 51C Medico-social Problems in Ankylosing Spondylitics R. Leung, P. Leung, E. Ho Leung, P. Ho, E. 53D Clinical Psychological Problems in Ankylosing Spondylitics P. Leung, P. Lee, F. L. Mak, E. Ho Leung, P. Lee, P. Mak, F. L. Ho, E. 57E Study On Pain in Ankylosing Spondylitics C. Hsu Hsu, C. 65i Cauda Equina Syndrome E. Ho, M. Yuen, L. Ma, L.C.S. Hsu Ho, E. Yeun, M. Ma, L. Hsu, L. C. S.ii O.P.L.L. and A.S. With Traumatic Tetraparesis E. Ho, J.C.Y. Leong Ho, E. Leong, J. C. Y
Why Speed Doesn’t Kill: Learning to Believe in Disinflation
No full textCentral bankers generally prefer to reduce inflation gradually. We show that a central bank may try to convince the private sector of its commitment to price stability by choosing to reduce inflation quickly. We call this "teaching by doing". We find that allowing for teaching by doing effects always speeds up the disinflation and leads to lower inflation persistence. So, we clarify why "speed" in the disinflation process does not necessarily "kill" in the sense of creating large output losses. This result also holds in an environment where private agents learn about the central bank’s inflation target using a constant gain algorithm.learning, disinflation, credibility, sacrifice ratio
Meta-analyses of STIs and hepatitis infections prevalence among broader MSM comparing among HIV-positive MSM and male sex workers in China.
No full textφ<p>Some studies reported more than one prevalence estimate (e.g. in multiple years or locations). The number of estimates represents the total number of data points analysed in meta-analysis.</p>#<p>The estimated prevalence for HIV, syphilis and HIV-syphilis co-infection were extracted from a published meta-analysis study by Chow EPF <i>et al</i> in 2011.</p>∧<p>The broader MSM population was used as the reference group for odds ratio.</p><p>*<i>p</i><0.05, **<i>p</i><0.01, ***<i>p</i><0.001.</p
Writing and the rights of reality: usurpation and potentiality in Derrida, Plato, Nietzsche, and Beckett
No full textThe thesis critically evaluates Jacques Derrida's conferral of the rights of reality on writing, focussing on his theory of an arche-text in light of the speculative nature of this theory. The theory is initially considered in the context of Derrida's elucidation of the usurpatory status of writing within the Platonic and Nietzschean texts. This consideration reveals an admission of writing's usurpatory status by both writers while at the same time demonstrating their awareness of the intrinsically speculative nature of this view, the significance of writing lying in its ability to exteriorise the radically indeterminate status of consciousness m relation to reality rather than its ability to displace consciousness or reality The analyses, therefore, not only bring the Derridean hypothesis of a repressive or phonocentric metaphysical episteme into question but also exhibit the historical and philosophical role of potentiality in relation to writing, writing's ultimate significance lying in its capacity to exteriorise our existence as a mode of potentiality. Accordingly, in the second half of the thesis the Derridean theory of writing is countered with a specifically Aristotelian theory of the text as it is exhibited in the prose of Samuel Beckett, an author whose significance lies in his close alignment with Derridean theory within contemporary criticism. It is demonstrated that this identification has obviated an awareness of the significance of potentiality within the Beckettian text, his work consequently being appraised in the previously neglected context of Aristotelian metaphysics
- …
