Interpolation by a Game
From MaRDI portal
Publication:4224078
DOI10.1002/malq.19980440403zbMath0915.03047OpenAlexW2142326240MaRDI QIDQ4224078
Publication date: 5 July 1999
Published in: Mathematical Logic Quarterly (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/malq.19980440403
propositional formulasproof systemsHall's theoreminterpolation theoremsreal gamereal communication complexitysize of monotone real formulas and circuitstree-like monotone protocols
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes ⋮ Randomized feasible interpolation and monotone circuits with a local oracle ⋮ Dag-like communication and its applications ⋮ Some consequences of cryptographical conjectures for \(S_2^1\) and EF ⋮ A note on monotone real circuits ⋮ Unnamed Item ⋮ Depth lower bounds in Stabbing Planes for combinatorial principles ⋮ Equality alone does not simulate randomness ⋮ A feasible interpolation for random resolution
Cites Work
