5 citations · 7 across the 4 of their papers we have counts for
4 papers · 1 filter
Proving Unsatisfiability with Hitting Formulas
Yuval Filmus, Edward A. Hirsch, Artur Riazanov +2
Hitting formulas have been studied in many different contexts at least since [Iwama,89]. A hitting formula is a set of Boolean clauses such that any two of them cannot be simultane…
The power of the Binary Value Principle
Yaroslav Alekseev, Edward A. Hirsch
The (extended) Binary Value Principle (eBVP: for and ) has received a lot of attention recently, several lower bounds have been prov…
Semi-Algebraic Proofs, IPS Lower Bounds and the -Conjecture: Can a Natural Number be Negative?
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch +1
We introduce the binary value principle which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems…
On optimal heuristic randomized semidecision procedures, with application to proof complexity
Edward A. Hirsch, Dmitry Itsykson
The existence of a (p-)optimal propositional proof system is a major open question in (proof) complexity; many people conjecture that such systems do not exist. Krajicek and Pudlak…