Almost tight lower bounds on regular resolution refutations of Tseitin Formulas for all constant-degree graphs - TIB AV-Portal

Almost tight lower bounds on regular resolution refutations of Tseitin Formulas for all constant-degree graphs

00:00

2

Zugehöriges Material

Banff International Research Station (BIRS) for Mathematical Innovation and Discovery

Itsykson, Dmitry

Formale Metadaten

Titel

Almost tight lower bounds on regular resolution refutations of Tseitin Formulas for all constant-degree graphs

Alternativer Titel

On 1-BP complexity of satisfiable Tseitin formulas and how it relates to regular resolution

Serientitel

Proof Complexity (20w5144)

Anzahl der Teile

27

Autor

Itsykson, Dmitry

Lizenz

CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.

Identifikatoren

10.5446/55823 (DOI)

Herausgeber

Banff International Research Station (BIRS) for Mathematical Innovation and Discovery

Erscheinungsjahr

Sprache

Inhaltliche Metadaten

Fachgebiet	Informatik Mathematik
Genre	Workshop/Interaktives Format Vorlesung

Serie

Proof Complexity (20w5144)21 / 27

1

56:48

Proof Complexity 2020

2

53:29

Semialgebraic Proofs and Efficient Algorithm Design

3

51:52

Hardness Condensation

4

28:43

Polynomial Calculus Space and Resolution Width

5

25:21

Size-Degree Trade-Off for Sums-of-Squares Proofs

6

35:06

(Semi)Algebraic Proofs over {±1} Variables

7

55:12

On Depth 1 Frege Systems

8

1:00:05

Semi-Algebraic Proofs, IPS Lower Bounds and the τ -Conjecture: Can a Natural Number be Negative?

9

28:01

Consistency of Circuit Lower Bounds with Bounded Theories

10

28:49

Why are Proof Complexity Lower Bounds Hard?

11

29:50

Characterising QBF Hardness via Circuit Complexity

12

30:41

Sum of Squares Bounds for the Ordering Principle

13

30:56

Resolution and the binary encodings of combinatorial principles

14

27:43

The Surprising Power of Constant Depth Algebraic Proofs

15

51:44

Lifting Applied to Proof Complexity

16

50:31

Automating Resolution is NP-Hard

17

45:31

Automated Proof Search: The Aftermath

18

28:34

Resolution Lower Bounds for Refutation Statements

19

25:23

SETH and Resolution

20

31:20

Reversible Pebble Games and the Relation between Tree-like and General Resolution Space

21

28:49

Almost tight lower bounds on regular resolution refutations of Tseitin Formulas for all constant-degree graphs

22

22:14

k-Clique and Regular vs. General Resolution

23

28:14

Exponential Resolution Lower Bounds for the Weak Pigeonhole Principle over Sparse Graphs

24

29:37

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

25

30:12

Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs

26

30:52

Proof Complexity of Systems of (Non-Deterministic) Decision Trees and Branching Programs

27

25:10

Hard Examples for Common Variable Decision Heuristics

Automatisches Abspielen