Search results for "Bounded arithmetic"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Evan Goris	Feasible Operations on Proofs: The Logic of Proofs for Bounded Arithmetic.	Theory Comput. Syst.	2008	DBLP DOI BibTeX RDF	Logic of proofs, Bounded arithmetic
3	Olaf Beyersdorff, Sebastian Müller	A Tight Karp-Lipton Collapse Result in Bounded Arithmetic.	CSL	2008	DBLP DOI BibTeX RDF	Karp-Lipton Theorem, Optimal Propositional Proof Systems, Extended Frege, Bounded Arithmetic, Advice
3	Andrés Cordón-Franco, Alejandro Fernández-Margarit, Francisco Félix Lara Martín	On Rules and Parameter Free Systems in Bounded Arithmetic.	CiE	2007	DBLP DOI BibTeX RDF	conservation results, parameter free schemes, Bounded Arithmetic
3	Masahiro Yasumoto	Separations of first and second order theories in bounded arithmetic.	Arch. Math. Log.	2005	DBLP DOI BibTeX RDF	Separation, Bounded Arithmetic
3	Alan Skelley	A Third-Order Bounded Arithmetic Theory for PSPACE.	CSL	2004	DBLP DOI BibTeX RDF	quantified propositional calculus, Bounded arithmetic, PSPACE, propositional proof complexity
3	Jan Johannsen	Weak Bounded Arithmetic, the Diffie-Hellman Problem and Constable's Class K.	LICS	1999	DBLP DOI BibTeX RDF	feasible interpolation, cryptographic hardness assumption, function algebra, bounded arithmetic, implicit computational complexity, Diffie-Hellman problem
2	Klaus Aehlig, Arnold Beckmann	On the Computational Complexity of Cut-Reduction.	LICS	2008	DBLP DOI BibTeX RDF	cut-reduction, proof notations, propositional logic, Bounded Arithmetic
2	Satoru Kuroda	Generalized quantifier and a bounded arithmetic theory for LOGCFL.	Arch. Math. Log.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 03F30, 68Q15
2	Leszek Aleksander Kolodziejczyk, Neil Thapen	The Polynomial and Linear Hierarchies in V0.	CiE	2007	DBLP DOI BibTeX RDF	prefix parity, linear hierarchy, bounded depth circuits, bounded arithmetic
2	Morteza Moniri	Preservation theorems for bounded formulas.	Arch. Math. Log.	2007	DBLP DOI BibTeX RDF	Polynomial induction, Model completeness, Universal theory, Quantifier elimination, Intuitionistic logic, NP, Bounded arithmetic, Polynomial hierarchy, Kripke model
2	Evan Goris	Logic of Proofs for Bounded Arithmetic.	CSR	2006	DBLP DOI BibTeX RDF
2	Antonina Kolokolova	Closure Properties of Weak Systems of Bounded Arithmetic.	CSL	2005	DBLP DOI BibTeX RDF
2	Arnold Beckmann	Resolution Refutations and Propositional Proofs with Height-Restrictions.	CSL	2002	DBLP DOI BibTeX RDF	Height of proofs, Length of proofs, Resolution refutation, Frege systems, Order induction principle, Cut introduction, MSC: Primary 03F20, Secondary 03F07, 68R99, Cut elimination, 68Q15, Bounded arithmetic, Propositional calculus
2	Arnold Beckmann	A Note on Universal Measures for Weak Implicit Computational Complexity.	LPAR	2002	DBLP DOI BibTeX RDF	Dynamic ordinals, Witness oracle TURING machines, Weak implicit computational complexity, Bounded arithmetic
2	Martin Hofmann	From Bounded Arithmetic to Memory Management: Use of Type Theory to Capture Complexity Classes and Space Behaviour.	TLCA	2001	DBLP DOI BibTeX RDF
2	Albert Atserias	Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms.	MFCS	2001	DBLP DOI BibTeX RDF	Weak Pigeonhole Principle, Proof Complexity, Bounded Arithmetic
2	Mitsuru Tada, Makoto Tatsuta	The function ëa/mû\lfloor a/m\rfloor in sharply bounded arithmetic.	Arch. Math. Log.	1997	DBLP DOI BibTeX RDF
2	Alexander A. Razborov	Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic.	ICALP	1996	DBLP DOI BibTeX RDF
1	Pavel Pudlák, Neil Thapen	Alternating minima and maxima, Nash equilibria and Bounded Arithmetic.	Ann. Pure Appl. Logic	2012	DBLP DOI BibTeX RDF
1	Yoriyuki Yamagata	Bounded Arithmetic in Free Logic	CoRR	2012	DBLP BibTeX RDF
1	Leszek Aleksander Kolodziejczyk, Phuong Nguyen, Neil Thapen	The provably total NP search problems of weak second order bounded arithmetic.	Ann. Pure Appl. Logic	2011	DBLP DOI BibTeX RDF
1	Emil Jerábek	A sorting network in bounded arithmetic.	Ann. Pure Appl. Logic	2011	DBLP DOI BibTeX RDF
1	Emil Jerábek	On theories of bounded arithmetic for NC1.	Ann. Pure Appl. Logic	2011	DBLP DOI BibTeX RDF
1	Neil Thapen	Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem.	Arch. Math. Log.	2011	DBLP DOI BibTeX RDF
1	Zofia Adamowicz, Leszek Aleksander Kolodziejczyk	A note on the Sigma1 collection scheme and fragments of bounded arithmetic.	Math. Log. Q.	2010	DBLP DOI BibTeX RDF
1	António M. Fernandes	Strict P11-reflection in bounded arithmetic.	Arch. Math. Log.	2010	DBLP DOI BibTeX RDF
1	Olaf Beyersdorff, Sebastian Müller	A tight Karp-Lipton collapse result in bounded arithmetic.	ACM Trans. Comput. Log.	2010	DBLP DOI BibTeX RDF
1	Richard Pettigrew	On Interpretations of Bounded Arithmetic and Bounded Set Theory.	Notre Dame Journal of Formal Logic	2009	DBLP BibTeX RDF
1	Emil Jerábek	Approximate counting by hashing in bounded arithmetic.	J. Symb. Log.	2009	DBLP BibTeX RDF
1	Charalampos Cornaros, Alan R. Woods	On bounded arithmetic augmented by the ability to count certain sets of primes.	J. Symb. Log.	2009	DBLP BibTeX RDF
1	Andrés Cordón-Franco, Alejandro Fernández-Margarit, Francisco Félix Lara Martín	Existentially Closed Models and Conservation Results in Bounded Arithmetic.	J. Log. Comput.	2009	DBLP DOI BibTeX RDF
1	Olaf Beyersdorff, Sebastian Müller	Does Advice Help to Prove Propositional Tautologies?	SAT	2009	DBLP DOI BibTeX RDF
1	Pavel Pudlák	Fragments of bounded arithmetic and the lengths of proofs.	J. Symb. Log.	2008	DBLP BibTeX RDF
1	Morteza Moniri	On the Hierarchy of Intuitionistic Bounded Arithmetic.	J. Log. Comput.	2008	DBLP DOI BibTeX RDF
1	Antonina Kolokolova	Many Facets of Complexity in Logic.	CiE	2008	DBLP DOI BibTeX RDF
1	Phuong Nguyen	Proving Infinitude of Prime Numbers Using Binomial Coefficients.	CSL	2008	DBLP DOI BibTeX RDF
1	Jan Krajícek, Alan Skelley, Neil Thapen	NP search problems in low fragments of bounded arithmetic.	J. Symb. Log.	2007	DBLP BibTeX RDF
1	Emil Jerábek	Approximate counting in bounded arithmetic.	J. Symb. Log.	2007	DBLP BibTeX RDF
1	Alan Skelley	Third-Order Computation and Bounded Arithmetic.	J. Log. Comput.	2007	DBLP DOI BibTeX RDF
1	Zofia Adamowicz, Leszek Aleksander Kolodziejczyk	Partial collapses of the Sigma1 complexity hierarchy in models for fragments of bounded arithmetic.	Ann. Pure Appl. Logic	2007	DBLP DOI BibTeX RDF
1	Phuong Nguyen, Stephen A. Cook	The Complexity of Proving the Discrete Jordan Curve Theorem.	LICS	2007	DBLP DOI BibTeX RDF
1	Leszek Aleksander Kolodziejczyk	On the Herbrand notion of consistency for finitely axiomatizable fragments of bounded arithmetic theories.	J. Symb. Log.	2006	DBLP BibTeX RDF
1	Morteza Moniri	An Independence Result for Intuitionistic Bounded Arithmetic.	J. Log. Comput.	2006	DBLP DOI BibTeX RDF
1	Constantinos Bartzis, Tevfik Bultan	Efficient BDDs for bounded arithmetic constraints.	STTT	2006	DBLP DOI BibTeX RDF	Model checking, BDD, Integer arithmetic, SMV
1	Stephen A. Cook, Neil Thapen	The strength of replacement in weak arithmetic.	ACM Trans. Comput. Log.	2006	DBLP DOI BibTeX RDF	cryptography, PV, Bounded arithmetic
1	Morteza Moniri	Polynomial induction and length minimization in intuitionistic bounded arithmetic.	Math. Log. Q.	2005	DBLP DOI BibTeX RDF
1	Arnold Beckmann, Jan Johannsen	An unexpected separation result in Linearly Bounded Arithmetic.	Math. Log. Q.	2005	DBLP DOI BibTeX RDF
1	Neil Thapen	Structures interpretable in models of bounded arithmetic.	Ann. Pure Appl. Logic	2005	DBLP DOI BibTeX RDF
1	Kerry Ojakian	Upper and lower Ramsey bounds in bounded arithmetic.	Ann. Pure Appl. Logic	2005	DBLP DOI BibTeX RDF
1	Stephen A. Cook, Tsuyoshi Morioka	Quantified propositional calculus and a second-order theory for NC1.	Arch. Math. Log.	2005	DBLP DOI BibTeX RDF	Computational Complexity, Proof Complexity, Bounded Arithmetic
1	Eugenio Chinchilla	Models of replacement schemes.	Arch. Math. Log.	2005	DBLP DOI BibTeX RDF
1	Neil Thapen, Michael Soltys	Weak theories of linear algebra.	Arch. Math. Log.	2005	DBLP DOI BibTeX RDF
1	Jirí Hanika	Herbrandizing search problems in Bounded Arithmetic.	Math. Log. Q.	2004	DBLP DOI BibTeX RDF
1	Arnold Beckmann	Preservation theorems and restricted consistency statements in bounded arithmetic.	Ann. Pure Appl. Logic	2004	DBLP DOI BibTeX RDF
1	Aleksandar Ignjatovic, Arun Sharma	Some applications of logic to feasibility in higher types.	ACM Trans. Comput. Log.	2004	DBLP DOI BibTeX RDF	higher-order complexity, second-order theories, functionals, bounded arithmetic
1	Stephen A. Cook, Antonina Kolokolova	A Second-Order Theory for NL.	LICS	2004	DBLP DOI BibTeX RDF
1	Olaf Beyersdorff	Representable Disjoint NP-Pairs.	FSTTCS	2004	DBLP DOI BibTeX RDF
1	Jan Krajícek	Combinatorics of first order structures and propositional proof systems.	Arch. Math. Log.	2004	DBLP DOI BibTeX RDF
1	Arnold Beckmann, Chris Pollett, Samuel R. Buss	Ordinal notations and well-orderings in bounded arithmetic.	Ann. Pure Appl. Logic	2003	DBLP DOI BibTeX RDF
1	Arnold Beckmann, Samuel R. Buss, Chris Pollett	Erratum to "Ordinal notations and well-orderings in bounded arithmetic" [Annals of Pure and Applied Logic 120 (2003) 197-223].	Ann. Pure Appl. Logic	2003	DBLP DOI BibTeX RDF
1	Constantinos Bartzis, Tevfik Bultan	Construction of Efficient BDDs for Bounded Arithmetic Constraints.	TACAS	2003	DBLP DOI BibTeX RDF
1	Helger Lipmaa	On Diophantine Complexity and Statistical Zero-Knowledge Arguments.	ASIACRYPT	2003	DBLP DOI BibTeX RDF	Arguments of knowledge, Diophantine complexity, integer commitment scheme, statistical zero knowledge
1	Arnold Beckmann	Dynamic ordinal analysis.	Arch. Math. Log.	2003	DBLP DOI BibTeX RDF
1	Russell Impagliazzo, Jan Krajícek	A Note on Conservativity Relations among Bounded Arithmetic Theories.	Math. Log. Q.	2002	DBLP DOI BibTeX RDF
1	Chris Pollett	Nepomnjascij's Theorem and Independence Proofs in Bounded Arithmetic	Electronic Colloquium on Computational Complexity (ECCC)	2002	DBLP BibTeX RDF
1	Arnold Beckmann	Proving Consistency of Equational Theories in Bounded Arithmetic.	J. Symb. Log.	2002	DBLP BibTeX RDF
1	Aleksandar Ignjatovic	A Note on Induction Schemas in Bounded Arithmetic	CoRR	2002	DBLP BibTeX RDF
1	Satoru Kuroda	An Independence Result on Weak Second Order Bounded Arithmetic.	Math. Log. Q.	2001	DBLP DOI BibTeX RDF
1	Tsuyoshi Morioka	Classification of Search Problems and Their Definability in Bounded Arithmetic	Electronic Colloquium on Computational Complexity (ECCC)	2001	DBLP BibTeX RDF
1	Gaisi Takeuti	Gödel Sentences of Bounded Arithmetic.	J. Symb. Log.	2000	DBLP BibTeX RDF
1	Toshiyasu Arai	A Bounded Arithmetic AID for Frege Systems.	Ann. Pure Appl. Logic	2000	DBLP DOI BibTeX RDF
1	Achim Blumensath	Bounded Arithmetic and Descriptive Complexity.	CSL	2000	DBLP DOI BibTeX RDF	arithmetic, descriptive complexity, definability
1	Samuel R. Buss	Bounded Arithmetic, Proof Complexity and Two Papers of Parikh.	Ann. Pure Appl. Logic	1999	DBLP DOI BibTeX RDF
1	Chris Pollett	Structure and Definability in General Bounded Arithmetic Theories.	Ann. Pure Appl. Logic	1999	DBLP DOI BibTeX RDF
1	Mario Chiari, Jan Krajícek	Lifting independence results in bounded arithmetic.	Arch. Math. Log.	1999	DBLP DOI BibTeX RDF
1	Jan Johannsen	A Remark an Independence Results for Sharply Bounded Arithmetic.	Math. Log. Q.	1998	DBLP BibTeX RDF
1	Mario Chiari, Jan Krajícek	Witnessing Functions in Bounded Arithmetic and Search Problems.	J. Symb. Log.	1998	DBLP BibTeX RDF
1	Gaisi Takeuti, Masahiro Yasumoto	Forcing on Bounded Arithmetic II.	J. Symb. Log.	1998	DBLP BibTeX RDF
1	Jan Krajícek	Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic.	J. Symb. Log.	1997	DBLP BibTeX RDF
1	Domenico Zambella	End Extensions of Models of Linearly Bounded Arithmetic.	Ann. Pure Appl. Logic	1997	DBLP DOI BibTeX RDF
1	Domenico Zambella	Notes on Polynomially Bounded Arithmetic.	J. Symb. Log.	1996	DBLP BibTeX RDF
1	Samuel R. Buss	Relating the Bounded Arithmetic and Polynomial Time Hierarchies.	Ann. Pure Appl. Logic	1995	DBLP DOI BibTeX RDF
1	Samuel R. Buss, Aleksandar Ignjatovic	Unprovability of Consistency Statements in Fragments of Bounded Arithmetic.	Ann. Pure Appl. Logic	1995	DBLP DOI BibTeX RDF
1	Gaisi Takeuti	Separations of Theories in Weak Bounded Arithmetic.	Ann. Pure Appl. Logic	1995	DBLP DOI BibTeX RDF
1	Alexander A. Razborov	Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract).	MFCS	1995	DBLP DOI BibTeX RDF
1	Rineke Verbrugge, Albert Visser	A Small Reflection Principle for Bounded Arithmetic.	J. Symb. Log.	1994	DBLP BibTeX RDF
1	Alessandro Berarducci, Rineke Verbrugge	On the Provability Logic of Bounded Arithmetic.	Ann. Pure Appl. Logic	1993	DBLP DOI BibTeX RDF
1	Victor Harnik	Provably Total Functions of Intuitionistic Bounded Arithmetic.	J. Symb. Log.	1992	DBLP BibTeX RDF
1	Peter Clote, Gaisi Takeuti	Bounded Arithmetic for NC, ALogTIME, L and NL.	Ann. Pure Appl. Logic	1992	DBLP DOI BibTeX RDF
1	Spyro-Giorgio Mantzivis	Circuits in Bounded Arithmetic, Part I.	Ann. Math. Artif. Intell.	1992	DBLP DOI BibTeX RDF
1	Jan Krajícek, Pavel Pudlák, Gaisi Takeuti	Bounded Arithmetic and the Polynomial Hierarchy.	Ann. Pure Appl. Logic	1991	DBLP DOI BibTeX RDF
1	Jan Krajícek	Exponentiation and Second-Order Bounded Arithmetic.	Ann. Pure Appl. Logic	1990	DBLP DOI BibTeX RDF
1	Pavel Pudlák	Ramsey's Theorem in Bounded Arithmetic.	CSL	1990	DBLP DOI BibTeX RDF
1	Peter Clote	Bounded Arithmetic and Computational Complexity.	Structure in Complexity Theory Conference	1990	DBLP BibTeX RDF
1	Samuel R. Buss	The Polynomial Hierarchy and Intuitionistic Bounded Arithmetic.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
1	Peter Clote, Gaisi Takeuti	Exponential Time and Bounded Arithmetic.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
1	Samuel R. Buss	The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended Abstract)	STOC	1985	DBLP DOI BibTeX RDF
1	Keith Harrow	The Bounded Arithmetic Hierarchy	Information and Control	1978	DBLP DOI BibTeX RDF