This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set.
Contents
Part I. Basic Complexity Classes: 1. The computational model - and why it doesn’t matter; 2. NP and NP completeness; 3. Diagonalization; 4. Space complexity; 5. The polynomial hierarchy and alternations; 6. Boolean circuits; 7. Randomized computation; 8. Interactive proofs; 9. Cryptography; 10. Quantum computation; 11. PCP theorem and hardness of approximation: an introduction; Part II. Lower Bounds for Concrete Computational Models: 12. Decision trees; 13. Communication complexity; 14. Circuit lower bounds; 15. Proof complexity; 16. Algebraic computation models; Part III. Advanced Topics: 17. Complexity of counting; 18. Average case complexity: Levin’s theory; 19. Hardness amplification and error correcting codes; 20. Derandomization; 21. Pseudorandom constructions: expanders and extractors; 22. Proofs of PCP theorems and the Fourier transform technique; 23. Why are circuit lower bounds so difficult?; Appendix A: mathematical background.
Reviews
Pre-Publication Review: "This text is a major achievement that brings together all of the important developments in complexity theory. Student and researchers alike will find it to be an immensely useful resource."
Michael Sipser, MIT, author of Introduction to the Theory of Computation
Pre-Publication Review: "Computational complexity theory is at the core of theoretical computer science research. This book contains essentially all of the (many) exciting developments of the last two decades, with high level intuition and detailed technical proofs. It is a must for everyone interested in this field."
Avi Wigderson, Professor, Institute for Advanced Study, Princeton
Pre-Publication Review: "This book by two leading theoretical computer scientists provides a comprehensive,insightful and mathematically precise overview of computational complexity theory, ranging from early foundational work to emerging areas such as quantum computation and hardness of approximation. It will serve the needs of a wide audience, ranging from experienced researchers to graduate students and ambitious undergraduates seeking an introduction to the mathematical foundations of computer science. I will keep it at my side as a useful reference for my own teaching and research."
Richard M. Karp, University Professor, University of California at Berkeley

The standard rules of probability can be interpreted as uniquely valid principles in logic. In this book, E. T. Jaynes dispels the imaginary distinction between 'probability theory' and 'statistical inference', leaving a logical unity and simplicity, which provides greater technical power and flexibility in applications. This book goes beyond the conventional mathematics of probability theory, viewing the subject in a wider context. New results are discussed, along with applications of probability theory to a wide variety of problems in physics, mathematics, economics, chemistry and biology. It contains many exercises and problems, and is suitable for use as a textbook on graduate level courses involving data analysis. The material is aimed at readers who are already familiar with applied mathematics at an advanced undergraduate level or higher. The book will be of interest to scientists working in any area where inference from incomplete information is necessary.

In this textbook, Michael Morris offers a critical introduction to the central issues of the philosophy of language. Each chapter focusses on one or two texts which have had a seminal influence on work in the subject, and uses these as a way of approaching both the central topics and the various traditions of dealing with them. Texts include classic writings by Frege, Russell, Kripke, Quine, Davidson, Austin, Grice and Wittgenstein. Theoretical jargon is kept to a minimum and is fully explained whenever it is introduced. The range of topics covered includes sense and reference, definite descriptions, proper names, natural-kind terms, de re and de dicto necessity, propositional attitudes, truth-theoretical approaches to meaning, radical interpretation, indeterminacy of translation, speech acts, intentional theories of meaning, and scepticism about meaning. The book will be invaluable to students and to all readers who are interested in the nature of linguistic meaning.

Hannah Arendt was one of the foremost political thinkers of the twentieth century, and her particular interests have made her one of the most frequently cited thinkers of our time. This volume examines the primary themes of her multi-faceted work, from her theory of totalitarianism and her controversial idea of the "banality of evil" to her classic studies of political action and her final reflections on judgment and the life of the mind. Each essay examines the political, philosophical, and historical concerns that shaped Arendt's thought.

The Italian opera company in Prague managed by Pasquale Bondini and Domenico Guardasoni played a central role in promoting Mozart's operas during the final years of his life. Using a wide range of primary sources which include the superb collections of eighteenth-century opera posters and concert programmes in Leipzig and the Indice de' teatrali spettacoli, an almanac of Italian singers and dancers, this study examines the annual schedules, recruitment networks, casting policies and repertoire selections of this important company. Woodfield shows how Italian-language performances of Figaro, Don Giovanni, Cosi fan tutte and La clemenza di Tito flourished along the well-known cultural axis linking Prague in Bohemia to Dresden and Leipzig in Saxony. The important part played by concert performances of operatic arias in the early reception of Mozart's works is also discussed and new information is presented about the reception of Josepha Duschek and Mozart in Leipzig.

《全球冷战》令人印象深刻的地方就是作者驾驭多边档案史料的功底。在书中，文安立不但使用了公开出版的史料集、回忆录、博士论文及其他二手资料，而且触摸了大量为世人所不了解的多边档案，其中了包括了俄罗斯（苏联）、中国、塞尔维亚和黑山、意大利、德国、美国和南非等数国，涉及了多种所在国语言。这充分体现了 作者高超的语言使用能力和史料梳理技艺，令人赞叹。在充分的事实基础上，作者为我们详细地描述了美苏两国干涉第三世界国家的全景史画，并突出了二者彼此相异的意识形态诉求和策略手段。而且，他将笔触一直延伸至21世纪初的当代世界，顺流直下，将干涉史的影响与当代国际热点问题紧密、妥当地联系在一起，显现了其炽热的现实关怀热情。

Biolinguistics involves the study of language from a broad perspective that embraces natural sciences, helping us better to understand the fundamentals of the faculty of language. This Handbook offers the most comprehensive state-of-the-field survey of the subject available. A team of prominent scholars working in a variety of disciplines is brought together to examine language development, language evolution and neuroscience, as well as providing overviews of the conceptual landscape of the field. The Handbook includes work at the forefront of contemporary research devoted to the evidence for a language instinct, the critical period hypothesis, grammatical maturation, bilingualism, the relation between mind and brain and the role of natural selection in language evolution. It will be welcomed by graduate students and researchers in a wide range of disciplines, including linguistics, evolutionary biology and cognitive science.

Humans instinctively form words by weaving patterns of meaningless speech elements. Moreover, we do so in specific, regular ways. We contrast dogs and gods, favour blogs to lbogs. We begin forming sound-patterns at birth and, like songbirds, we do so spontaneously, even in the absence of an adult model. We even impose these phonological patterns on invented cultural technologies such as reading and writing. But why are humans compelled to generate phonological patterns? And why do different phonological systems - signed and spoken - share aspects of their design? Drawing on findings from a broad range of disciplines including linguistics, experimental psychology, neuroscience and comparative animal studies, Iris Berent explores these questions and proposes a new hypothesis about the architecture of the phonological mind.

The quest for freedom from hunger and repression has triggered in recent years a dramatic, worldwide reform of political and economic systems. Never have so many people enjoyed, or at least experimented with democratic institutions. However, many strategies for economic development in Eastern Europe and Latin America have failed with the result that entire economic systems on both continents are being transformed. This major book analyzes recent transitions to democracy and market-oriented economic reforms in Eastern Europe and Latin America. Drawing in a quite distinctive way on models derived from political philosophy, economics, and game theory, Professor Przeworski also considers specific data on individual countries. Among the questions raised by the book are: What should we expect from these experiments in democracy and market economy? What new economic systems will emerge? Will these transitions result in new democracies or old dictatorships?

China has one of the longest continuous literary traditions in the world. From the beginnings of the Chinese written language to the lively world of internet literature, these two volumes tell the story of Chinese writing, both as an instrument of the state and as a medium for culture outside the state. The chapters, organized chronologically, treat not only poetry, drama, and fiction, but also historical writing and other prose forms. Written by internationally recognized experts in the field, the History frequently challenges current scholarship, from taking recent archeological discoveries into consideration to understanding Chinese modernity not as a sudden rupture with the past but as part of a longer process. The History offers both an integrated narrative, situating literature in its larger cultural context, and an overview of the key developments of the past millennia accessible to non-specialist readers as well as scholars and students of Chinese.
Contents
Volume I: Introduction;
1. Early Chinese literature: beginnings through Western Han Martin Kern;
2. From the Eastern Han through the Western Jin (AD 25–317) David Knechtges;
3. From the Eastern Jin through the Early Tang (317–649) Xiaofei Tian;
4. The Cultural Tang (650–1020) Stephen Owen;
5. The Northern Song (1020–1126) Ronald Egan;
6. North and South: the twelfth and thirteenth centuries Michael Fuller and Shuen-fu Lin;
7. Literature from the Late Jin to the Early Ming: ca. 1230–ca. 1375 Stephen H. West; Bibliography; Glossary;
Index; Volume II: Introduction;
1. Literature of the Early Ming to Mid-Ming (1375–1572) Kang-i Sun Chang;
2. The literary culture of the Late Ming (1573–1644) Tina Lu;
3. Early Qing to 1723 Wai-yee Li;
4. The Literati Era and its demise (1723–1840) Shang Wei;
5. Prosimetric and verse narrative Wilt L. Idema;
6. Chinese literature from 1841 to 1937 David Der-wei Wang, Jing Tsu and Michel Hockx;
7. Chinese literature from 1937 to the present Michelle Yeh, Jing Tsu and Michel Hockx; Bibliography; Glossary; Index.

The relationship between language and ideology has long been central to research in discourse analysis, pragmatics, sociolinguistics and linguistic anthropology, and has also informed other fields such as sociology and literary criticism. This book, by one of the world's leading pragmatists, introduces a new framework for the study of ideology in written language, using the tools, methods and theories of pragmatics and discourse analysis. Illustrations are drawn systematically from a coherent corpus of excerpts from late nineteenth- and early twentieth-century history textbooks dealing with episodes of colonial history and in particular the 1857 'Indian Mutiny'. It includes the complete corpus of excerpts, allowing researchers and students to evaluate all illustrations; at the same time, it provides useful practice and training materials. The book is intended as a teaching tool in language-, discourse- and communication-oriented programs, but also for historians and social and political scientists.

This ground breaking study dispels the common belief that Chinese 'doesn't have words' but instead 'has characters'. Jerome Packard's book provides a comprehensive discussion of the linguistic and cognitive nature of Chinese words. It shows that Chinese, far from being 'morphologically impoverished', has a different morphological system because it selects different 'settings' on parameters shared by all languages. The analysis of Chinese word formation therefore enhances our understanding of word universals. Packard describes the intimate relationship between words and their components, including how the identities of Chinese morphemes are word-driven, and offers new insights into the evolution of morphemes based on Chinese data. Models are offered for how Chinese words are stored in the mental lexicon and processed in natural speech, showing that much of what native speakers know about words occurs innately in the form of a hard-wired, specifically linguistic 'program' in the brain.

This book offers a concise survey of basic probability theory from a thoroughly subjective point of view whereby probability is a mode of judgment. Written by one of the greatest figures in the field of probability theory, the book is both a summation and synthesis of a lifetime of wrestling with these problems and issues. After an introduction to basic probability theory, there are chapters on scientific hypothesis-testing, on changing your mind in response to generally uncertain observations, on expectations of the values of random variables, on de Finetti's dissolution of the so-called problem of induction, and on decision theory.

Bernard Spolsky looks at the many debates at the forefront of language policy in this up-to-date introduction. The topics covered include ideas of correctness and bad language; bilingualism and multilingualism; language death and efforts to preserve endangered languages; language choice as a human and civil right; and language education policy. Spolsky develops a theory of modern national language policy and the major forces controlling it and explores questions that arise concerning the recognition of language policies and language management.

The Opium War of 1839-42, the first military conflict to take place between China and the West, is a subject of enduring interest. Mao Haijian, one of the most distinguished and well-known historians working in China, presents the culmination of more than ten years of research in a revisionist reading of the conflict and its main Chinese protagonists. Mao examines the Qing participants in terms of the moral standards and intellectual norms of their own time, demonstrating that actions which have struck later observers as ridiculous can be understood as reasonable within these individuals' own context. This English-language translation of Mao's work offers a comprehensive response to the question of why the Qing Empire was so badly defeated by the British in the first Opium War - an answer that is distinctive and original within both Chinese and Western historiography, and supported by a wealth of hitherto unknown detail.

While the comparative method is concerned with regularities in phonological change, grammaticalization theory deals with regularities of grammatical change. In an A-Z format, this book summarizes the most salient generalizations that have been made on the unidirectional change of grammatical forms and constructions. It thus demonstrates that grammatical change is regular and also adds to our knowledge of universal properties of human languages. Indices organized by source and target concepts allow for flexible use, and the findings delineated in the book are relevant to students of language across theoretical boundaries.

Over the last two years, wavelet methods have shown themselves to be of considerable use to harmonic analysts and, in particular, advances have been made concerning their applications. The strength of wavelet methods lies in their ability to describe local phenomena more accurately than a traditional expansion in sines and cosines can. Thus, wavelets are ideal in many fields where an approach to transient behaviour is needed, for example, in considering acoustic or seismic signals, or in image processing. Yves Meyer stands the theory of wavelets firmly upon solid ground by basing his book on the fundamental work of Calderon, Zygmund and their collaborators. For anyone who would like an introduction to wavelets, this book will prove to be a necessary purchase.

Schenker's Interpretive Practice is the first comprehensive study of this century's most influential music theorist, Heinrich Schenker. Since the 1960s, American theorists and musicologists have focused almost exclusively on analytical methods distilled from Schenker's writings. Breaking from that tradition, Robert Snarrenberg returns to Schenker's texts and to the humanist roots of his approach, situating Schenker's work in the broader context of his desire to portray the richness and particularity of musical experience. Snarrenberg concentrates on four aims that Schenker hoped to achieve: to present a theoretical account of musical effects encountered in European music of the eighteenth and nineteenth centuries, to represent the mindset shared among composers of that music, to convey the expressive interaction of musical effects in individual artwork, and to promote continued creative and re-creative participation in the musical tradition. Author recipient of the 1998 Young Scholar Award from the Society of Music Theory.