The combinatorial parity principle states that there is no perfect matching on an odd number of vertices. This principle generalizes the pigeonhole principle, which states that for a fixed bipartition of the vertices, there is no perfect matching between them. Therefore, it follows from recent lower bounds for the pigeonhole principle that the parity principle requires exponential-size bounded-depth Frege proofs. Ajtai previously showed that the parity principle does not have polynomial-size bounded-depth Frege proofs even with the pigeonhole principle as an (...) axiom schema. His proof utilizes nonstandard model theory and is nonconstructive. We improve Ajtai's lower bound from barely superpolynomial to exponential and eliminate the nonstandard model theory. Our lower bound is also related to the inherent complexity of particular search classes . In particular, oracle separations between the complexity classes PPA and PPAD, and between PPA and PPP also follow from our techniques. (shrink)

Resolution is the most widely studied approach to propositional theorem proving. In developing efficient resolution-based algorithms, dozens of variants and refinements of resolution have been studied from both the empirical and analytic sides. The most prominent of these refinements are: DP (ordered). DLL (tree), semantic, negative, linear and regular resolution. In this paper, we characterize and study these six refinements of resolution. We give a nearly complete characterization of the relative complexities of all six refinements. While many of the important (...) separations and simulations were already known, many new ones are presented in this paper: in particular, we give the first separation of semantic resolution from general resolution. As a special case, we obtain the first exponential separation of negative resolution from general resolution. We also attempt to present a unifying framework for studying all of these refinements. (shrink)

The method of analytic tableaux is employed in many introductory texts and has also been used quite extensively as a basis for automated theorem proving. In this paper, we discuss the complexity of the system as a method for refuting contradictory sets of clauses, and resolve several open questions. We discuss the three forms of analytic tableaux: clausal tableaux, generalized clausal tableaux, and binary tableaux. We resolve the relative complexity of these three forms of tableaux proofs and also resolve the (...) relative complexity of analytic tableaux versus resolution. We show that there is a quasi-polynomial simulation of tree resolution by analytic tableaux; this simulation is close to optimal, since we give a matching lower bound that is tight to within a polynomial. (shrink)

We consider small-weight Cutting Planes (CP * ) proofs; that is, Cutting Planes (CP) proofs with coefficients up to $\operatorname{Poly}(n)$ . We use the well known lower bounds for monotone complexity to prove an exponential lower bound for the length of CP * proofs, for a family of tautologies based on the clique function. Because Resolution is a special case of small-weight CP, our method also gives a new and simpler exponential lower bound for Resolution. We also prove the following (...) two theorems: (1) Tree-like CP * proofs cannot polynomially simulate non-tree-like CP * proofs. (2) Tree-like (CP * proofs and Bounded-depth-Frege proofs cannot polynomially simulate each other. Our proofs also work for some generalizations of the CP * proof system. In particular, they work for CP * with a deduction rule, and also for any proof system that allows any formula with small communication complexity, and any set of sound rules of inference. (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)

Savant aux intérêts multiples--historiques, scientifiques et religieux, connu et estimé dans l'Europe du XVIIIe siècle, bien qu'ayant très peu publié de son vivant, Firmin Abauzit reste à beaucoup d'égards un mystère. Comment ce réfugié huguenot, arrivé à Genève encore enfant après la révocation de l'édit de Nantes, a-t-il pu bénéficier d'une réputation flatteuse dans la ville d'accueil alors que ses opinions hétérodoxes sur la trinité ou la christologie ou les prophéties bibliques étaient notoires? Au-delà des étiquettes faciles, quelle était la (...) nature exacte de son hétérodoxie? Comment sa légendaire 'modestie', qui lui a fait refuser honneurs et charges publiques, se concilie-t-elle avec le fait de laisser copier et circuler abondamment en Europe ses manuscrits? Quel rapport existe-t-il entre une telle circulation et son refus obstiné d'autoriser la publication de ses travaux? Comment interpréter, dans son cas, la tension entre réputation et publication? À ces questions, souvent escamotées ou abordées dans une visée hagiographique, le volume répond par une réflexion large qui croise l'histoire des religions, de la littérature, de la philosophie et du fait religieux. Une approche qui intègre des aspects peu ou pas du tout étudiés de la vaste production de l'auteur, tels que le rapport entre idolâtrie et religion, ou sa lecture de textes déistes anglais, ou encore ses écrits de controverse confessionnelle, mais qui reprend aussi, en les renouvelant, des thèmes plus classiques, comme la célèbre note de Rousseau sur Abauzit philosophe ou les éditions concurrentes qui ont été publiées peu après la mort du savant"--Page 4 of cover. (shrink)

The present article traces the changes that took place within the Genevan church between the late seventeenth and early eighteenth centuries. These changes resulted from a number of different factors, but especially from the evolution in theological and other, broader intellectual parameters. The analysis focuses on the spirited debates that surrounded the Consensus Helveticus, a formula which was adopted in Geneva in 1679 and to which all pastors were required to subscribe. When the Genevan church decided in 1706 no longer (...) to require subscription, it did so – among others – for the freedom of conscience on articles not necessary to salvation, and thus embarked on a long road of theological reflection which led it eventually to abandon, within the space of only several decades, the orthodox theology that had dominated the seventeenth century. As result of this evolution, the eighteenth century saw a slow but definite change in the image the church of Geneva held for the rest of European Calvinism. ☆ This article is an uptated English translation of «De l’exemplarité au soupçon: l’Eglise genevoise entre la fin du XVIIe siècle et le début du XVIIIe» in W. Kaiser, C. Sieber-Lehmann et C. Windler (éd.), Eidgenössische «Grenzfälle»: Mülhausen und Genf/en marge de la Confédération: Mulhouse et Genève (Basler Beiträge zur Geschichtswissenschaft 172), Bâle, Schwabe et Co, 2001, 273–92. I thank Keith Tribe for his translation and Albert Gootjes for his suggestions for updating. (shrink)

La question de la légitimité et de la faisabilité de l’examen religieux – l’un des sujets principaux de la controverse confessionnelle en France au XVIIe siècle – traverse l’ensemble du corpus baylien. Étroitement lié à des questions cruciales comme celle de la nature des vérités divines, des dispositions éthiques du croyant et du statut de la Bible, l’examen religieux est en réalité pour Bayle un oxymore, qui tente de concilier ce qui est antithétique, à savoir l’examen philosophique et la croyance.

Issu des travaux présentés dans le cadre d'une journée d'étude sur le malebranchisme, organisée en novembre 2015 par l'Institut d'histoire de la Réformation de l'Université de Genève, cet ouvrage propose une relecture de la philosophie de Malebranche à travers le kaléidoscope des controverses et des réceptions qu'elle a inspirées. Les contributions réunies dans le volume explorent, d'un côté, l'impact que les querelles ont eu sur le développement du malebranchisme et leur écho chez les prétendus héritiers de cette philosophie ; de (...) l'autre, la réception contemporaine de certains philosophèmes malebranchiens ainsi que, inversement, les modalités d'assimilation par l'auteur de théories incontournables pour la pensée moderne. (shrink)

We study the complexity of proving the Pigeon Hole Principle in a monotone variant of the Gentzen Calculus, also known as Geometric Logic. We prove a size-depth trade-off upper bound for monotone proofs of the standard encoding of the PHP as a monotone sequent. At one extreme of the trade-off we get quasipolynomia -size monotone proofs, and at the other extreme we get subexponential-size bounded-depth monotone proofs. This result is a consequence of deriving the basic properties of certain monotone formulas (...) computing the Boolean threshold functions. We also consider the monotone sequent expressing the Clique-Coclique Principle defined by Bonet, Pitassi and Raz [9]. We show that monotone proofs for this sequent can be easily reduced to monotone proofs of the one-to-one and onto PHP, and so CLIQUE also has quasipolynomia -size monotone proofs. As a consequence of our results, Resolution, Cutting Planes with polynomially bounded coefficients, and Bounded-Depth Frege are exponentially separated from the monotone Gentzen Calculus. Finally, a simple simulation argument implies that these results extend to the Intuitionistic Gentzen Calculus. Our results partially answer some questions left open by P. Pudlák. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:Reviewed by:Pierre Bayle dans la République des Lettres: Philosophie, Religion, CritiqueJosé R. Maia NetoAntony McKenna and Gianni Paganini, editors. Pierre Bayle dans la République des Lettres: Philosophie, Religion, Critique. Paris: Honoré Champion, 2004. Pp. 589. Cloth, €90.00.Pierre Bayle is an early modern philosopher who has received relatively little attention given the philosophical relevance and historical influence of his work. Fortunately this situation has been rapidly changing in recent years. (...) This volume, edited by Antony McKenna and Gianni Paganini, is a good sample of the volume, quality, scope, and polemical nature of current Bayle scholarship. The book contains twenty-five articles by the main Bayle scholars from France, Italy, England, the Netherlands, Canada, and the United States. It also contains an introduction by the editors, who give an overview of current scholarship, summarizing its main trends and achievements, and a useful name index. The articles are organized in five sections, each dealing with some aspect of Bayle's life and thought.The first set of articles, gathered under the heading, "Interlocutors, Friends and Enemies," deals with Bayle's personal relations as a Huguenot exiled in the Netherlands. Luisa Simonutti deals with Bayle's relations to one of the radical Reformed groups in Holland, the Quakers. Although Bayle disagreed with their religious views, he respected and maintained [End Page 476] healthy intellectual exchanges with them. Hans Bots examines Bayle's view of the "republic of letters," of which he was a major architect—a republic whose right to citizenship required the suspension of religious, political, and national partisanship and engagement in free intellectual debate. H. H. M. van Lieshout contests the entrenched view that Bayle lived as a recluse scholar in Rotterdam. Both she and Bots show how Bayle's main work, the Dictionary, exhibits his life committed to the "republic of letters." Finally, Hubert Bost focuses on Bayle's activity as a journalist, crucial in this republic but also revealing the difficulty of the pursued ideal of neutrality.The next three sections of the book deal with Bayle's thoughts on religion and philosophy. Anna Belgrado denies the late Bayle scholar Elizabeth Labrousse's thesis that Bayle's thought is wrought with Protestantism. Bayle's views on the Jews, the Middle Ages, and women are examined, respectively, by Myrian Yardeni, Gregorio Piaia, and Maria-Cristina Pitassi, who concur in concluding that, although not free from the prejudices of his time, Bayle's views are more complex and balanced than those of his contemporaries.Bayle's political views and in particular his view on tolerance receive a good deal of attention in the volume. Stefano Brogi explains Bayle's attack on the "rational theologians" (Le Clerc), at first sight puzzling given their defense of religious tolerance, pointing out Bayle's radical opposition between faith and reason. According to Jean-Michel Gros, it is this radical separation of philosophy from theology that renders Bayle's view of tolerance so modern, unlike Locke's, for instance, which still has a theological ground. Jonathan Israel explains another apparent puzzle: Bayle's defense of absolute monarchism despite his philosophical and religious ideas, which were no less radical than Spinoza's. Bayle, unlike Spinoza, does not support republicanism because of his pessimistic view of human nature. John Christian Laursen shows that the political menace posed by the Millenarians explains Bayle's unusual lack of tolerance towards them.One of the most influential contemporary Bayle scholars, Gianluca Mori, summarizes his view of Bayle as a philosophical atheist, and he is contested in this by Jean-Luc Solère, who argues that for Bayle, materialism does not provide a coherent metaphysical system alternative to the Christian one, so that Bayle's position amounts to a radical skepticism with regard to reason. In his contribution to the volume, Mori argues that Bayle's skepticism is restricted, and is not relevant to the issue of theism versus atheism. He replies to Solère's objections to his interpretation in an appendix to his article. Mori's interpretation relies on the method of reading Bayle's text as containing irreligious views hidden beneath apparently orthodox claims. Thomas Lennon relies on the opposite approach to argue... (shrink)

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.

In lieu of an abstract, here is a brief excerpt of the content:Reviewed by:Pierre Bayle dans la République des Lettres: Philosophie, Religion, CritiqueJosé R. Maia NetoAntony McKenna and Gianni Paganini, editors. Pierre Bayle dans la République des Lettres: Philosophie, Religion, Critique. Paris: Honoré Champion, 2004. Pp. 589. Cloth, €90.00.Pierre Bayle is an early modern philosopher who has received relatively little attention given the philosophical relevance and historical influence of his work. Fortunately this situation has been rapidly changing in recent years. (...) This volume, edited by Antony McKenna and Gianni Paganini, is a good sample of the volume, quality, scope, and polemical nature of current Bayle scholarship. The book contains twenty-five articles by the main Bayle scholars from France, Italy, England, the Netherlands, Canada, and the United States. It also contains an introduction by the editors, who give an overview of current scholarship, summarizing its main trends and achievements, and a useful name index. The articles are organized in five sections, each dealing with some aspect of Bayle's life and thought.The first set of articles, gathered under the heading, "Interlocutors, Friends and Enemies," deals with Bayle's personal relations as a Huguenot exiled in the Netherlands. Luisa Simonutti deals with Bayle's relations to one of the radical Reformed groups in Holland, the Quakers. Although Bayle disagreed with their religious views, he respected and maintained [End Page 476] healthy intellectual exchanges with them. Hans Bots examines Bayle's view of the "republic of letters," of which he was a major architect—a republic whose right to citizenship required the suspension of religious, political, and national partisanship and engagement in free intellectual debate. H. H. M. van Lieshout contests the entrenched view that Bayle lived as a recluse scholar in Rotterdam. Both she and Bots show how Bayle's main work, the Dictionary, exhibits his life committed to the "republic of letters." Finally, Hubert Bost focuses on Bayle's activity as a journalist, crucial in this republic but also revealing the difficulty of the pursued ideal of neutrality.The next three sections of the book deal with Bayle's thoughts on religion and philosophy. Anna Belgrado denies the late Bayle scholar Elizabeth Labrousse's thesis that Bayle's thought is wrought with Protestantism. Bayle's views on the Jews, the Middle Ages, and women are examined, respectively, by Myrian Yardeni, Gregorio Piaia, and Maria-Cristina Pitassi, who concur in concluding that, although not free from the prejudices of his time, Bayle's views are more complex and balanced than those of his contemporaries.Bayle's political views and in particular his view on tolerance receive a good deal of attention in the volume. Stefano Brogi explains Bayle's attack on the "rational theologians" (Le Clerc), at first sight puzzling given their defense of religious tolerance, pointing out Bayle's radical opposition between faith and reason. According to Jean-Michel Gros, it is this radical separation of philosophy from theology that renders Bayle's view of tolerance so modern, unlike Locke's, for instance, which still has a theological ground. Jonathan Israel explains another apparent puzzle: Bayle's defense of absolute monarchism despite his philosophical and religious ideas, which were no less radical than Spinoza's. Bayle, unlike Spinoza, does not support republicanism because of his pessimistic view of human nature. John Christian Laursen shows that the political menace posed by the Millenarians explains Bayle's unusual lack of tolerance towards them.One of the most influential contemporary Bayle scholars, Gianluca Mori, summarizes his view of Bayle as a philosophical atheist, and he is contested in this by Jean-Luc Solère, who argues that for Bayle, materialism does not provide a coherent metaphysical system alternative to the Christian one, so that Bayle's position amounts to a radical skepticism with regard to reason. In his contribution to the volume, Mori argues that Bayle's skepticism is restricted, and is not relevant to the issue of theism versus atheism. He replies to Solère's objections to his interpretation in an appendix to his article. Mori's interpretation relies on the method of reading Bayle's text as containing irreligious views hidden beneath apparently orthodox claims. Thomas Lennon relies on the opposite approach to argue... (shrink)