a computational proof of complexity of some restricted counting problems

South Central University

The Effect of Indexing on the Complexity of Object Recognition

Many current recognition systems use constrained search to locate objects in cluttered environments. Previous formal analysis has shown that the expected amount of search is quadratic in the number of model and data features, if all the data is known to come from a sinlge object, but is exponential when spurious data is included. If one can group the data into subsets likely to have come from a single object, then terminating the search once a "good enough" interpretation is found reduces the expected search to cubic. Without successful grouping, terminated search is still exponential. These results apply to finding instances of a known object in the data. In this paper, we turn to the problem of selecting models from a library, and examine the combinatorics of determining that a candidate object is not present in the data. We show that the expected search is again exponential, implying that naﶥ approaches to indexing are likely to carry an expensive overhead, since an exponential amount of work is needed to week out each of the incorrect models. The analytic results are shown to be in agreement with empirical data for cluttered object recognition.

On the Relationship Between Generalization Error, Hypothesis Complexity, and Sample Complexity for Radial Basis Functions

In this paper, we bound the generalization error of a class of Radial Basis Function networks, for certain well defined function learning tasks, in terms of the number of parameters and number of examples. We show that the total generalization error is partly due to the insufficient representational capacity of the network (because of its finite size) and partly due to insufficient information about the target function (because of finite number of samples). We make several observations about generalization error which are valid irrespective of the approximation scheme. Our result also sheds light on ways to choose an appropriate network architecture for a particular problem.

Wendt, IR and Philosophy: A Critique

Suganami, Hidemi, 'Wendt, IR and Philosophy: A Critique', In: 'Constructivism and International Relations: Alexander Wendt and His Critics', (New York: Routledge), pp.57-72, 2006 RAE2008

Ludwig Feuerbach's Critique of Religion and the End of Moral Philosophy

Williams, H. (2006). Ludwig Feuerbach's Critique of Religion and the End of Moral Philosophy. In Moggach, D. (Ed.), The New Hegelians: Politics and Philosophy in the Hegelian School (pp.50-66). Cambridge: Cambridge University Press. Introduction; Part I. Eduard Gans: 1. Eduard Gans on poverty and on the constitutional debate; 2. Ludwig Feuerbach's Critique of Religion and the end of moral philosophy; Part II. Ludwig Feuerbach: 3. The symbolic dimension and the politics of Left Hegelianism; Part III. Bruno Bauer: 4. Exclusiveness and political universalism in Bruno Bauer; 5. Republican rigorism and emancipation in Bruno Bauer; Part IV. Edgar Bauer: 6. Edgar Bauer and The Origins of the Theory of Terrorism; Max Stirner 7. Ein Menschenleben: Hegel and Stirner; 8. 'The State and I': Max Stirner's anarchism; Friedrich Engels: 9. Engels and the invention of the catastrophist conception of the industrial revolution; Karl Marx: 10. The basis of the state in the Marx of 1842; 11. Marx and Feuerbachian essence: returning to the question of 'Human Essence' in historical materialism; 12. Freedom and the 'Realm of Necessity'; Concluding with Hegel :13. Work, language and community: a response to Hegel's critics. RAE2008

Appreciating ecological complexity: Habitat contours as a conceptual landscape model

Joern Fischer, David B. Lindermayer, and Ioan Fazey (2004). Appreciating Ecological Complexity: Habitat Contours as a Conceptual Landscape Model. Conservation Biology, 18 (5)pp.1245-1253 RAE2008

Konstrukcje tożsamości i bogactwo kulturowe w autobiografiach Güntera Grassa i Marcela Reicha-Ranickiego jako wyzwanie translatorskie

Wydział Neofilologii: Instytut Filologii Germańskiej

A Short History of Computational Complexity

National Science Foundation (CCR-998310); Army Research Office (DAAD19-02-1-0058)

On the Complexity of Quantum ACC

For any q > 1, let MOD_q be a quantum gate that determines if the number of 1's in the input is divisible by q. We show that for any q,t > 1, MOD_q is equivalent to MOD_t (up to constant depth). Based on the case q=2, Moore has shown that quantum analogs of AC^(0), ACC[q], and ACC, denoted QAC^(0)_wf, QACC[2], QACC respectively, define the same class of operators, leaving q > 2 as an open question. Our result resolves this question, implying that QAC^(0)_wf = QACC[q] = QACC for all q. We also prove the first upper bounds for QACC in terms of related language classes. We define classes of languages EQACC, NQACC (both for arbitrary complex amplitudes) and BQACC (for rational number amplitudes) and show that they are all contained in TC^(0). To do this, we show that a TC^(0) circuit can keep track of the amplitudes of the state resulting from the application of a QACC operator using a constant width polynomial size tensor sum. In order to accomplish this, we also show that TC^(0) can perform iterated addition and multiplication in certain field extensions.

"A Good Reder": the middle English Wise Book of Philosophy and Astronomy, instruction, publics, and manuscripts

The present work is a study of the Middle English prose text known as The Wise Book of Philosophy and Astronomy, a consideration of its transmission and reception history, and a survey of its manuscript witnesses; it also incorporates an edition of the text from two of its manuscripts. The text is a cosmological treatise of approximately five thousand words, written for the most part in English, with astronomical and astrological terms in Latin, though the English translation is frequently given. It is written anonymously, and survives in thirty-three manuscripts.

Max Stirner's relevance to contemporary philosophy: a critical analysis

The aim of this dissertation is to revive the 19th-century thinker Max Stirner’s thought through a critical reexamination of his mistaken legacy as a ‘political’ thinker. The reading of Stirner that I present is one of an ontological thinker, spurred on as much—if not more—by the contents of Hegel’s Phenomenology of Spirit as it is the radical roots that Hegel unintentionally planted. In the first chapter, the role of language in Stirner’s thought is examined, and the problems to which his conception of language seem to give rise are addressed. The second chapter looks at Stirner’s purportedly ‘anarchistic’ politics and finds the ‘anarchist’ reading of Stirner misguided. Rather than being a ‘political’ anarchist, it is argued that we ought to understand Stirner as advocating a sort of ‘ontological’ anarchism in which the very existence of authority is questioned. In the third chapter, I look at the political ramifications of Stirner’s ontology as well as the critique of liberalism contained within it, and argue that the politics implicit in his philosophy shares more in common with the tradition of political realism than it does anarchism. The fourth chapter is dedicated to an examination of Stirner’s anti-humanism, which is concluded to be much different than the ‘anti-humanisms’ associated with other, more famous thinkers, such as Foucault and Heidegger. In the fifth and final chapter, I provide an answer to the question(s) of how, if, and to what extent Friedrich Nietzsche was influenced by Stirner. It is concluded that the complete lack of evidence that Nietzsche ever read Stirner is proof enough to dismiss accusations of plagiarism on Nietzsche’s part, thus emphasizing the originality and singularity of both thinkers.

The political philosophy of Miki Kiyoshi: A close reading of the philosophical foundations of cooperative communitarianism

The thesis is a historical and philological study of the mature political theory of Miki Kiyoshi (1897-1945) focused on Philosophical Foundations of Cooperative Communitarianism (1939), a full translation of which is included. As the name suggests, it was a methodological and normative communitarianism, which critically built on liberalism, Marxism and Confucianism to realise a regional political community. Some of Miki’s Western readers have wrongly considered him a fascist ideologue, while he has been considered a humanist Marxist in Japan. A closer reading cannot support either view. The thesis argues that the Anglophone study of Japanese philosophy is a degenerating research programme ripe for revolution in the sense of returning full circle to an original point. That means returning to the texts, reading them contextually and philologically, in principle as early modern European political theory is read by intellectual historians, such as the representatives of Cambridge School history of political thought. The resulting reading builds critically on the Japanese scholarship and relates it to contemporary Western and postcolonial political theory and the East Asian tradition, particularly neo-Confucianism. The thesis argues for a Cambridge School perspective radicalised by the critical addendum of geo-cultural context, supplemented by Geertzian intercultural hermeneutics and a Saidian ‘return to philology’. As against those who have seen radical reorientations in Miki’s political thought, the thesis finds gradual progression and continuity between his neo-Kantian, existentialist, Marxian anthropology, Hegelian and finally communitarian phases. The theoretical underpinnings are his philosophical anthropology, a structurationist social theory of praxis, and a critique of liberalism, Marxism, nationalism and idealism emphasising concrete as opposed to abstract theory and the need to build on existing cultural traditions to modernise rather than westernise East Asia. This post-Western fusion was imagined to be the beginning of a true and pluralistic universalism.

Zazen, philosophy of mind, and the practicality of realising impermanence

This dissertation involves a general overview of the meditative practice of zazen and analytic philosophy of mind while suggesting a potential bridge between them in the form of an analysis of the practicality of realising impermanence. By the end of my argument I hope to have offered up some compelling evidence in favour of the idea that analytic philosophy would benefit greatly from adopting principles which are best learned and expressed through the practice of, and scholarship around, Zen Buddhism and in particular the treatment of the concept of impermanence. I demonstrate the Western philosophical tendency to make dichotomous assumptions about the nature of mind, even when explicitly denying a dualist framework. I do so by examining the historical and philosophical precedent for dualistic thinking in the work of figures such as Plato and Descartes. I expand on this idea by examining the psychology of categorisation - i.e. creating mental categories and boundaries - and demonstrating how such categorisations feeds back into behaviour in practical ways, both positive and negative. The Zen Buddhist principle of impermanence states that all phenomena are impermanent and therefore lack essential nature; this includes intellectual concepts such as the metaphysical framework of the analytic approach to mind. Impermanence is a principle which is realised through the embodied practice of zazen. By demonstrating its application to analytic philosophy of mind I show that zazen (and mindfulness practice in general) provides an ongoing opportunity for clearing up entrenched world views, metaphysical assumptions and dogmatic thinking. This in turn may promote a more holistic and ultimately more rewarding comprehension of the role of first-person experience in understanding the world. My argument is not limited to analytic philosophy of mind but reflects broad aspects of thinking in general, and I explain its application to issues of social importance, in particular education systems.