1 citations · 2 across the 9 of their papers we have counts for
Showing 2022 · cs.CCShow all
2 papers · 2 filters
cs.CC2022
On bounded depth proofs for Tseitin formulas on the grid; revisited
Johan Håstad, Kilian Risse
We study Frege proofs using depth- Boolean formulas for the Tseitin contradiction on grids. We prove that if each line in the proof is of size then the number o…
cs.CC2022★ 1 cited
Perfect Matching in Random Graphs is as Hard as Tseitin
Per Austrin, Kilian Risse
We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex bein…