Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size

Documenti analoghi

• Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
  di: de Rezende, Susanna F., et al.
  Pubblicazione: (2019)
• Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
  di: de Rezende, Susanna F., et al.
  Pubblicazione: (2024)
• Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
  di: Conneryd, Jonas, et al.
  Pubblicazione: (2025)
• On bounded depth proofs for Tseitin formulas on the grid; revisited
  di: Håstad, Johan, et al.
  Pubblicazione: (2022)
• Supercritical Tradeoffs for Monotone Circuits
  di: Göös, Mika, et al.
  Pubblicazione: (2024)