Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity

Documenti analoghi

• Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
  di: de Rezende, Susanna F., et al.
  Pubblicazione: (2026)
• Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
  di: de Rezende, Susanna F., et al.
  Pubblicazione: (2024)
• Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
  di: de Rezende, Susanna F., et al.
  Pubblicazione: (2024)
• Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
  di: Riazanov, Artur, et al.
  Pubblicazione: (2025)
• Better Boosting of Communication Oracles, or Not
  di: Harms, Nathaniel, et al.
  Pubblicazione: (2024)