We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [44], and show that this analysis can be formalized in the bounded arithmetic system VNC^1 (corresponding to the “NC^1 reasoning”). As a corollary, we prove the assumption made by Jeřábek [28] that a construction of certain bipartite expander graphs can be formalized in VNC^1 . This in turn implies that every proof in Gentzen's sequent calculus LK of a (...) monotone sequent can be simulated in the monotone version of LK (MLK) with only polynomial blowup in proof size, strengthening the quasipolynomial simulation result of Atserias, Galesi, and Pudlák [9]. (shrink)

This paper considers the computational complexity of the disjunction and existential properties of intuitionistic logic. We prove that the disjunction property holds feasibly for intuitionistic propositional logic; i.e., from a proof of A v B, a proof either of A or of B can be found in polynomial time. For intuitionistic predicate logic, we prove superexponential lower bounds for the disjunction property, namely, there is a superexponential lower bound on the time required, given a proof of A v B, to (...) produce one of A and B which is true. In addition, there is superexponential lower bound on the size of terms which fulfill the existential property of intuitionistic predicate logic. There are superexponential upper bounds for these problems, so the lower bounds are essentially optimal. (shrink)

We prove that the problem of determining the minimum propositional proof length is NP- hard to approximate within a factor of 2 log 1 - o(1) n . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution, Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length measured either by (...) number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problem and reduce it to the problems of approximation of the length of proofs. (shrink)

We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in both (...) classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees. (shrink)

We give a uniform proof of the theorems of Yao and Beigel–Tarui representing ACC predicates as constant depth circuits with MODm\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {MOD}_{m}$$\end{document} gates and a symmetric gate. The proof is based on a relativized, generalized form of Toda’s theorem expressed in terms of closure properties of formulas under bounded universal, existential and modular counting quantifiers. This allows the main proofs to be expressed in terms of formula classes instead of Boolean circuits. (...) The uniform version of the Beigel–Tarui theorem is then obtained automatically via the Furst–Saxe–Sipser and Paris–Wilkie translations. As a special case, we obtain a uniform version of Razborov and Smolensky’s representation of AC0[p]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {AC}^{0}[p]$$\end{document} circuits. The paper is partly expository, but is also motivated by the desire to recast Toda’s theorem, the Beigel–Tarui theorem, and their proofs into the language of bounded arithmetic. However, no knowledge of bounded arithmetic is needed. (shrink)

We introduce martingales defined by probabilistic strategies, in which randomness is used to decide whether to bet. We show that different criteria for the success of computable probabilistic strategies can be used to characterize ML-randomness, computable randomness, and partial computable randomness. Our characterization of ML-randomness partially addresses a critique of Schnorr by formulating ML randomness in terms of a computable process rather than a computably enumerable function.

We consider tautologies expressing equivalence‐chain properties in the spirit of Thapen and Krajíček, which are candidates for exponentially separating depth k and depth Frege proof systems. We formulate a special case where the initial member of the equivalence chain is fully specified and the equivalence‐chain implications are actually equivalences. This special case is shown to lead to polynomial size resolution refutations. Thus it cannot be used for separating depth k and depth propositional systems. We state some Håstad switching lemma conditions (...) that restrict the possible propositional proofs in more general situations. (shrink)

This paper studies the complexity of constant depth propositional proofs in the cedent and sequent calculus. We discuss the relationships between the size of tree-like proofs, the size of dag-like proofs, and the heights of proofs. The main result is to correct a proof construction in an earlier paper about transformations from proofs with polylogarithmic height and constantly many formulas per cedent.

We extend results of Bonet, Buss and Pitassi on Bondy’s Theorem and of Nozaki, Arai and Arai on Bollobás’ Theorem by proving that Frankl’s Theorem on the trace of sets has quasipolynomial size Frege proofs. For constant values of the parametert, we prove that Frankl’s Theorem has polynomial size AC0-Frege proofs from instances of the pigeonhole principle.

Many prominent critiques of philosophical methods proceed by suggesting that some method is unreliable, especially in comparison to some alternative method. In light of this, it may seem natural to conclude that these (comparatively) unreliable methods should be abandoned. Drawing upon work on the division of cognitive labour in science, we argue things are not so straightforward. Rather, whether an unreliable method should be abandoned depends heavily on the crucial question of how we should divide philosophers’ time and effort between (...) different methods, in order to maximise our prospects of achieving epistemic success. We show that, in a range of cases, even a (comparatively) unreliable method deserves to be allocated some of these resources. (shrink)

Capturing a scientific change in thinking about personality and individual differences that has been building over the past 15 years, this volume stands at an important moment in the development of psychology as a discipline. Rather than viewing individual differences as merely the raw material upon which selection operates, the contributing authors provide theories and empirical evidence which suggest that personality and individual differences are central to evolved psychological mechanisms and behavioral functioning. The book draws theoretical inspiration from life history (...) theory, evolutionary genetics, molecular genetics, developmental psychology, personality psychology, and evolutionary psychology, while utilizing the theories of the "best and the brightest" international scientists working on this cutting edge paradigm shift. In the first of three sections, the authors analyze personality and the adaptive landscape; here, the authors offer a novel conceptual framework for examining "personality assessment adaptations." Because individuals in a social environment have momentous consequences for creating and solving adaptive problems, humans have evolved "difference-detecting mechanisms" designed to make crucial social decisions such as mate selection, friend selection, kin investment, coalition formation, and hierarchy negotiation. In the second section, the authors examine developmental and life-history theoretical perspectives to explore the origins and development of personality over the lifespan. The third section focuses on the relatively new field of evolutionary genetics and explores which of the major evolutionary forces--such as balancing selection, mutation, co-evolutionary arms races, and drift--are responsible for the origins of personality and individual differences. Existing as a seminal work in the newly emerging evolutionary psychology field, this book is a "must-read" for anyone invested in the development of psychology as a field. (shrink)

Buss, S.R., The undecidability of k-provability, Annals of Pure and Applied Logic 53 75-102. The k-provability problem is, given a first-order formula ø and an integer k, to determine if ø has a proof consisting of k or fewer lines . This paper shows that the k-provability problem for the sequent calculus is undecidable. Indeed, for every r.e. set X there is a formula ø and an integer k such that for all n,ø has a proof of k sequents (...) if and only if n ε X. (shrink)

Ancient Confucianism and Daoism are distinct streams of thought, their differences stark at times. But they emerge from and flow through a shared cultural context and historical time. Certain common assumptions are to be found in each, and distinguish both from Western ways of thinking. This chapter considers the particulars of these two ancient Chinese perspectives, and the ways in which they differ from one another. The three key concepts of Confucianism include: humanity, duty, ritual. The Confucian worldview includes many (...) ideas and principles but these offer a starting point. The chapter recognizes Daoism's playful ambiguity and discusses the three concepts: Way (Dao), integrity (de), and non‐action (wuwei). (shrink)

We believe we owe one another respect. We believe we ought to pay what we owe by treating one another ‘with respect.’ If we could understand these beliefs we would be well on the way to understanding morality itself. If we could justify these beliefs we could vindicate a central part of our moral experience.Respect comes in many varieties. We respect some people for their upright character, others for their exceptional achievements. There are people we respect as forces of nature: (...) we go to great lengths to accommodate their moods, wiles, and demands. Finally, most of us seem to respect people simply because they are people. This is the sort of respect of special interest to moral theory.In order to be worthy of this last sort of respect, it is not only sufficient but necessary that one be a person. We can, of course, take a similar attitude towardnonpersons. (shrink)

Bestselling author Sam Harris dismantles the most common justification for religious faith-that a moral system cannot be based on science.

In this enlightening book, Sam Harris argues that free will is an illusion but that this truth should not undermine morality or diminish the importance of social and political freedom; indeed, this truth can and should change the way we think about some of the most important questions in life.

Inquiry aims at knowledge. Your inquiry into a question succeeds just in case you come to know the answer. However, combined with a common picture on which misleading evidence can lead knowledge to be lost, this view threatens to recommend a novel form of dogmatism. At least in some cases, individuals who know the answer to a question appear required to avoid evidence bearing on it. In this paper, we’ll aim to do two things. First, we’ll present an argument for (...) this novel form of dogmatism and show that it presents a substantive challenge. Second, we’ll consider a way those who take knowledge to be the aim of inquiry can mount a response. In the course of doing so, we’ll try to get clearer on the normative connections between inquiry, knowledge and evidence gathering. (shrink)

Sam Harris dismantles the most common justification for religious faith--that a moral system cannot be based on science.

Suppositional theories of conditionals take apparent similarities between supposition and conditionals as a starting point, appealing to features of the former to provide an account of the latter. This paper develops a novel form of suppositional theory, one which characterizes the relationship at the level of semantics rather than at the level of speech acts. In the course of doing so, it considers a range of novel data which shed additional light on how conditionals and supposition interact.

We develop a new version of the causal theory of spacetime. Whereas traditional versions of the theory seek to identify spatiotemporal relations with causal relations, the version we develop takes causal relations to be the grounds for spatiotemporal relations. Causation is thus distinct from, and more basic than, spacetime. We argue that this non-identity theory, suitably developed, avoids the challenges facing the traditional identity theory.

Facing challenges in your relationships, career, health or well-being? Worried important life goals seem to be slipping away? Whether you're faced with day-to-day irritations or facing a larger setback, sometimes life can test your strength and endurance. But there is a simple and effective way to building your resilience in the face of adversity, making sure that you can bounce back from them stronger than ever before and go on to achieve your goals and lead a happier, more fulfilled life. (...) This step-by-step guide takes you through how to build your everyday resilience. From powerful lessons on the effects of our thoughts, emotions, relationships and self-care, to tips on setting goals that genuinely motivate and turning challenges on their heads, it makes the road to success and happiness easy and - best of all - enjoyable. (shrink)

The curriculum design, faculty characteristics, and experience of implementing masters' level international research ethics training programs supported by the Fogarty International Center was investigated. Multiple pedagogical approaches were employed to adapt to the learning needs of the trainees. While no generally agreed set of core competencies exists for advanced research ethics training, more than 75% of the curricula examined included international issues in research ethics, responsible conduct of research, human rights, philosophical foundations of research ethics, and research regulation and ethical (...) review process. Common skills taught included critical thinking, research methodology and statistics, writing, and presentation proficiency. Curricula also addressed the cultural, social, and religious context of the trainees related to research ethics. Programs surveyed noted trainee interest in Western concepts of research ethics and the value of the transnational exchange of ideas. Similar faculty expertise profiles existed in all programs. Approximately 40% of faculty were female. Collaboration between faculty from low- and middleincome countries (LMICs) and high-income countries (HICs) occurred in most programs and at least 50% of HIC faculty had previous LMIC experience. This paper is part of a collection of papers analyzing the Fogarty International Research Ethics Education and Curriculum Development program. (shrink)

Think of a number, any number, or properties like fragility and humanity. These and other abstract entities are radically different from concrete entities like electrons and elbows. While concrete entities are located in space and time, have causes and effects, and are known through empirical means, abstract entities like meanings and possibilities are remarkably different. They seem to be immutable and imperceptible and to exist "outside" of space and time. This book provides a comprehensive critical assessment of the problems raised (...) by abstract entities and the debates about existence, truth, and knowledge that surround them. It sets out the key issues that inform the metaphysical disagreement between platonists who accept abstract entities and nominalists who deny abstract entities exist. Beginning with the essentials of the platonist–nominalist debate, it explores the key arguments and issues informing the contemporary debate over abstract reality: arguments for platonism and their connections to semantics, science, and metaphysical explanation the abstract–concrete distinction and views about the nature of abstract reality epistemological puzzles surrounding our knowledge of mathematical entities and other abstract entities. arguments for nominalism premised upon concerns about paradox, parsimony, infinite regresses, underdetermination, and causal isolation nominalist options that seek to dispense with abstract entities. Including chapter summaries, annotated further reading, and a glossary, _Entities_ is essential reading for anyone seeking a clear and authoritative introduction to the problems raised by abstract entities. (shrink)

Standard approaches to counterfactuals in the philosophy of explanation are geared toward causal explanation. We show how to extend the counterfactual theory of explanation to non-causal cases, involving extra-mathematical explanation: the explanation of physical facts by mathematical facts. Using a structural equation framework, we model impossible perturbations to mathematics and the resulting differences made to physical explananda in two important cases of extra-mathematical explanation. We address some objections to our approach.

Kant proclaimed that all theodicies must fail in ?On the Miscarriage of All Philosophical Trials in Theodicy?, but it is mysterious why he did so since he had developed a theodicy of his own during the critical period. In this paper, I offer an explanation of why Kant thought theodicies necessarily fail. In his theodicy, as well as in some of his works in ethics, Kant explained moral evil as resulting from unavoidable limitations in human beings. God could not create (...) finite beings without such limitations and so could not have created humans that were not prone to committing immoral acts. However, the work of Carl Christian Eberhard Schmid showed Kant that given his own beliefs about freedom and the nature of responsibility one could not account for moral evil in this way without tacitly denying that human beings were responsible for their actions. This result is significant not only because it explains an otherwise puzzling shift in Kant's philosophy of religion, but also because it shows that the theodicy essay provides powerful evidence that Kant's thinking about moral evil and freedom underwent fundamental shifts between early works such as the Groundwork and later works like the Religion within the Limits of Mere Reason. (shrink)

On a now orthodox view, humans and many other animals possess a “number sense,” or approximate number system, that represents number. Recently, this orthodox view has been subject to numerous critiques that question whether the ANS genuinely represents number. We distinguish three lines of critique – the arguments from congruency, confounds, and imprecision – and show that none succeed. We then provide positive reasons to think that the ANS genuinely represents numbers, and not just non-numerical confounds or exotic substitutes for (...) number, such as “numerosities” or “quanticals,” as critics propose. In so doing, we raise a neglected question: numbers of what kind? Proponents of the orthodox view have been remarkably coy on this issue. But this is unsatisfactory since the predictions of the orthodox view, including the situations in which the ANS is expected to succeed or fail, turn on the kind of number being represented. In response, we propose that the ANS represents not only natural numbers, but also non-natural rational numbers. It does not represent irrational numbers, however, and thereby fails to represent the real numbers more generally. This distances our proposal from existing conjectures, refines our understanding of the ANS, and paves the way for future research. (shrink)

The popularity of ‘food sovereignty’ to cover a range of positions, interventions, and struggles within the food system is testament, above all, to the term’s adaptability. Food sovereignty is centrally, though not exclusively, about groups of people making their own decisions about the food system—it is a way of talking about a theoretically-informed food systems practice. Since people are different, we should expect decisions about food sovereignty to be different in different contexts, albeit consonant with a core set of principles (...) (including women’s rights, a shared opposition to genetically modified crops, and a demand for agriculture to be removed from current international trade agreements). In this paper we look at the analytical points of friction in applying ideas of food sovereignty within the context of Indigenous struggles in North America. This, we argue, helps to clarify one of the central themes in food sovereignty: that it is a continuation of anti-colonial struggles, even in post-colonial contexts. Such an examination has dividends both for scholars of food sovereignty and for those of Indigenous politics: by helping to problematize notions of food sovereignty and postcoloniality, but also by posing pointed questions around gender for Indigenous struggles. (shrink)

The (re)building of the post-communist states offers new perspectives both on the state and on the multiple transitions that followed communism. Specifically, it shifts our analytical focus from states as consolidated outcomes and unitary actors to the process by which states come into being and into action in the modern era. This process consists of elite competition over policy-making authority, which is shaped and constrained by existing institutional resources, the pacing of transformation, and the international context. The four ideal types (...) of state-building that result are exemplified by the post-communist experience: democratic, autocratic, fractious, and personalistic. (shrink)

The theoretical virtue of parsimony values the minimizing of theoretical commitments, but theoretical commitments come in two kinds : ontological and ideological. While the ontological commitments of a theory are the entities it posits, a theory’s ideological commitments are the primitive concepts it employs. Here, I show how we can extend the distinction between quantitative and qualitative parsimony, commonly drawn regarding ontological commitments, to the domain of ideological commitments. I then argue that qualitative ideological parsimony is a theoretical virtue. My (...) defense proceeds by demonstrating the merits of qualitative ideological parsimony and by showing how the qualitative conception of ideological parsimony undermines two notable arguments from ideological parsimony: David Lewis’ defense of modal realism and Ted Sider’s defense of mereological nihilism. (shrink)