CCC 2015 accepted papers.

by Massimo Lauria

There will be a great Proof Complexity session at CCC2015.

  • Non-commutative formulas and Frege lower bounds: a new characterization of propositional proofs. Fu Li (Tsinghua University), Iddo Tzameret (Royal Holloway, University of London), Zhengyu Wang (Harvard University)
  • The space complexity of cutting planes refutations. Nicola Galesi (Sapienza University of Rome), Pavel Pudlák (Czech Academy of Sciences), Neil Thapen (Czech Academy of Sciences)
  • The functional pigeonhole principle requires polynomial calculus proofs of exponential size. Mladen Miksa (KTH Royal Institute of Technology), Jakob Nordstrom (KTH Royal Institute of Technology)
  • Tight size-degree lower bounds for sums-of-squares proofs. Massimo Lauria (KTH Royal Institute of Technology) Jakob Nordström (KTH Royal Institute of Technology)

See you all in Portland. If you come for STOC, no reason to miss CCC 2015!

CCC 2015 accepted papers.