FLoC2010 Logo

Propositional Proof Complexity: Theory and Practice

Workshop affiliated with the Federated Logic Conference (FLoC 2010)

Edinburgh, July 9, 2010


The topics of the workshop will be on propositional proof complexity in the widest sense with connections to applications for which complexity issues are essential and include (but are not restricted to):
  • Proof complexity of propositional proof systems: resolution, Frege systems, Nullstellensatz proofs etc.
  • Complexity measures for proofs
  • Automatizability of propositional proof systems
  • Monotone circuit complexity in relation to propositional proof complexity
  • Complexity of proof transformations
  • Algorithmic applications of proof complexity theory
  • Applications of games to propositional proof complexity