Pages that link to "Item:Q4027856"

The following pages link to Approximation and Small-Depth Frege Proofs (Q4027856):

Displaying 23 items.

• Exponential lower bounds for the pigeonhole principle (Q687506) (← links)
• Simplified lower bounds for propositional proofs (Q1374208) (← links)
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting (Q1377580) (← links)
• Hard examples for the bounded depth Frege proof system (Q1430570) (← links)
• Some remarks on lengths of propositional proofs (Q1908815) (← links)
• Bounded-depth Frege complexity of Tseitin formulas for all graphs (Q2084956) (← links)
• Hardness and optimality in QBF proof systems modulo NP (Q2118289) (← links)
• The canonical pairs of bounded depth Frege systems (Q2216035) (← links)
• Partially definable forcing and bounded arithmetic (Q2257103) (← links)
• Typical forcings, NP search problems and an extension of a theorem of Riis (Q2659102) (← links)
• Exponential lower bounds for \(\mathrm{AC}^0\)-Frege imply superpolynomial Frege lower bounds (Q2828228) (← links)
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs (Q2944908) (← links)
• Theories for subexponential-size bounded-depth Frege proofs (Q2958529) (← links)
• Forcing in Finite Structures (Q4351930) (← links)
• Formulas versus Circuits for Small Distance Connectivity (Q4554075) (← links)
• (Q4638077) (← links)
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle (Q4847394) (← links)
• A Logical Autobiography (Q5027230) (← links)
• Reflections on Proof Complexity and Counting Principles (Q5027248) (← links)
• Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs (Q5092411) (← links)
• On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies (Q5278196) (← links)
• (Q5465358) (← links)
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024 (Q6613418) (← links)