63 citations · 77 across the 15 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.CC2013★ 3 cited
Generating Matrix Identities and Proof Complexity
Fu Li, Iddo Tzameret
Motivated by the fundamental lower bounds questions in proof complexity, we initiate the study of matrix identities as hard instances for strong proof systems. A matrix identity of…
cs.CC2013
Sparser Random 3SAT Refutation Algorithms and the Interpolation Problem
Iddo Tzameret
We formalize a combinatorial principle, called the 3XOR principle, due to Feige, Kim and Ofek (2006), as a family of unsatisfiable propositional formulas for which refutations of s…