Search results for "proof-length"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
32	Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi	Minimum Propositional Proof Length is NP-Hard to Linearly Approximate.	MFCS	1998	DBLP DOI BibTeX RDF
27	Oded Goldreich 0001, Madhu Sudan 0001	Locally testable codes and PCPs of almost-linear length.	J. ACM	2006	DBLP DOI BibTeX RDF	error-correcting codes, derandomization, probabilistically checkable proofs, Proof verification
27	Oded Goldreich 0001, Madhu Sudan 0001	Locally Testable Codes and PCPs of Almost-Linear Length.	FOCS	2002	DBLP DOI BibTeX RDF
27	Mateja Jamnik, Manfred Kerber, Martin Pollet	Learn Omega-matic: System Description.	CADE	2002	DBLP DOI BibTeX RDF
26	Edward A. Hirsch, Sergey I. Nikolenko	Simulating Cutting Plane Proofs with Restricted Degree of Falsity by Resolution.	SAT	2005	DBLP DOI BibTeX RDF
24	Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah	Sound 3-Query PCPPs Are Long.	ICALP (1)	2008	DBLP DOI BibTeX RDF
21	Eli Ben-Sasson, Avi Wigderson	Short proofs are narrow - resolution made simple.	J. ACM	2001	DBLP DOI BibTeX RDF
21	Mauro Ferrari 0002, Camillo Fiorentini, Guido Fiorino	On the complexity of the disjunction property in intuitionistic and modal logics.	ACM Trans. Comput. Log.	2005	DBLP DOI BibTeX RDF	feasible interpolation, proof-length, modal logic, Intuitionistic logic
18	Arist Kojevnikov, Alexander S. Kulikov	Complexity of Semialgebraic Proofs with Restricted Degree of Falsity.	SAT	2006	DBLP DOI BibTeX RDF
17	Uwe Egly	Quantifers and the System KE: Some Surprising Results.	CSL	1998	DBLP DOI BibTeX RDF
15	Jedrzej Potoniec	Is the Proof Length a Good Indicator of Hardness for Reason-able Embeddings?	NeSy	2023	DBLP BibTeX RDF
15	Santiago Hernández-Orozco, Francisco Hernández Quiroz, Hector Zenil, Wilfried Sieg	Shortening of Proof Length is Elusive for Theorem Provers.	Parallel Process. Lett.	2020	DBLP DOI BibTeX RDF
15	Gustavo Lacerda	Upper-Bounding Proof Length with the Busy Beaver.	CoRR	2014	DBLP BibTeX RDF
15	Guillaume Burel	Unbounded Proof-Length Speed-Up in Deduction Modulo.	CSL	2007	DBLP DOI BibTeX RDF	rewriting, arithmetic, higher order logic, proof theory
15	Allen Van Gelder	Input Distance and Lower Bounds for Propositional Resolution Proof Length.	SAT	2005	DBLP DOI BibTeX RDF
15	Gilles Richard, Fatima Zohra Kettaf	Proof Length as an Uncertainty Factor in ILP.	Soft-Ware	2002	DBLP DOI BibTeX RDF
15	Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi	Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate.	J. Symb. Log.	2001	DBLP DOI BibTeX RDF
15	Uwe Egly	Non-elementary Speed-ups in Proof Length by Different Variants of Classical Analytic Calculi.	TABLEAUX	1997	DBLP DOI BibTeX RDF
15	Uwe Egly	Super-Polynomial Speed-Ups in Proof Length by New Tautologies.	EPIA	1995	DBLP DOI BibTeX RDF
15	Matthias Baaz, Christian G. Fermüller, Alexander Leitsch	A Non-Elementary Speed-Up in Proof Length by Structural Clause Form Transformation	LICS	1994	DBLP DOI BibTeX RDF
15	Thomas Marthedal Rasmussen	Automated Proof Support for Interval Logics.	LPAR	2001	DBLP DOI BibTeX RDF
11	Matthias Baaz, Georg Moser	On a Generalisation of Herbrand's Theorem.	CSL	2001	DBLP DOI BibTeX RDF
9	Jan Johannsen	An Exponential Lower Bound for Width-Restricted Clause Learning.	SAT	2009	DBLP DOI BibTeX RDF
9	Klaus Mayr	Refinements and Extensions of Model Elimination.	LPAR	1993	DBLP DOI BibTeX RDF
8	Uwe Egly	On the Value of Antiprenexing.	LPAR	1994	DBLP DOI BibTeX RDF
6	Adam L. Young, Moti Yung	A PVSS as Hard as Discrete Log and Shareholder Separability.	Public Key Cryptography	2001	DBLP DOI BibTeX RDF