Proof Complexity of Natural Formulas via Communication Arguments.

Dmitry Itsykson Artur Riazanov

Published in: Computational Complexity Conference (2021)

Keyphrases

computational complexity
communication networks
real world
man made
communication overhead
learning algorithm
np hard
worst case
information sharing
decision problems
communication systems
communication protocol
linear logic
polynomial hierarchy