Interpolation by a Game

DOI10.1002/MALQ.19980440403MaRDI QIDQ4224078zbMATH OpenOpenAlexFDO

Authors Jan Krajíček

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

zbMATH Keywords

propositional formulasHall's theoremproof systemsinterpolation theoremsreal gamereal communication complexitysize of monotone real formulas and circuitstree-like monotone protocols

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 3876457
• Interpolation†
• Interpolation
• Interpolation
• scientific article; zbMATH DE number 5270106
• Interpolation, preservation, and pebble games
• scientific article; zbMATH DE number 4147885
• scientific article; zbMATH DE number 4057896
• Interpolation via translations
• On almost interpolation

Cited in

(11)

• Depth lower bounds in Stabbing Planes for combinatorial principles
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• Equality alone does not simulate randomness
• On protocols for monotone feasible interpolation
• Stabbing planes
• A feasible interpolation for random resolution
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• A note on monotone real circuits
• Randomized feasible interpolation and monotone circuits with a local oracle
• Dag-like communication and its applications

This page was built for publication: Interpolation by a Game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4224078)