PC PROGRAM
Days: Saturday, July 12th Sunday, July 13th
Saturday, July 12th, 2014
View this program: with abstractssession overviewtalk overviewside by side with other conferences
10:15-10:45Coffee Break
10:45-12:00 Session 16A: PC Opening and Invited Talk (Pavel Pudlak)
Chair:
Location: FH, Seminarraum 101B
10:45 | Opening (abstract) |
11:00 | On Some Conjectures in Proof Complexity (abstract) |
12:00-13:00 Session 17B: Contributed Talks: SAT and QBF
Chair:
Location: FH, Seminarraum 101B
12:00 | Size-Space Bounds and Trade-offs for CDCL Proofs (abstract) |
12:30 | Beyond Q-Resolution and Prenex Form: A Proof System for Quantified Constraint Satisfaction (abstract) |
13:00-14:30Lunch Break
14:30-15:30 Session 18A: Invited Talk (Jakob Nordström)
Chair:
Location: FH, Seminarraum 101B
14:30 | A (Biased) Survey of Space Complexity and Time-Space Trade-offs in Proof Complexity (abstract) |
15:30-16:00 Session 19: Contributed Talk: Polynomial Calculus
Chair:
Location: FH, Seminarraum 101B
15:30 | Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds (abstract) |
16:00-16:30Coffee Break
16:30-18:00 Session 20A: Contributed Talks: Bounded Arithmetic
Chair:
Location: FH, Seminarraum 101B
16:30 | Provably Total Search Problems in Fragments of Bounded Arithmetic Below Polynomial-time (abstract) |
17:00 | Parameter-free induction in bounded arithmetic (abstract) |
17:30 | Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic (abstract) |
Sunday, July 13th, 2014
View this program: with abstractssession overviewtalk overviewside by side with other conferences
09:15-10:15 Session 24C: Contributed Talks: Proof Complexity
Chair:
Location: FH, Seminarraum 101B
09:15 | Quasipolynomial Size Frege Proofs of Frankl's Theorem on the Trace of Finite Sets (abstract) |
09:45 | n^O(log log n) size monotone proofs of the weak pigeonhole principle (abstract) |
10:15-10:45Coffee Break
10:45-11:45 Session 26N: Invited Talk (Albert Atserias)
Chair:
Location: FH, Seminarraum 101B
10:45 | Weak Pigeonhole Principles, Circuits for Approximate Counting, and Bounded-Depth Proofs (abstract) |
12:00-13:00 Session 29B: Contributed Talks: Resolution
Chair:
Location: FH, Seminarraum 101B
12:00 | Total Space in Resolution (abstract) |
12:30 | From Small Space to Small Width in Resolution (abstract) |
13:00-14:30Lunch Break
14:30-15:30 Session 31K: Invited Talk (Iddo Tzameret)
Chair:
Location: FH, Seminarraum 101B
14:30 | Are matrix identities hard instances for strong proof systems? (abstract) |
15:30-16:00 Session 33E: Contributed Talk: Complexity of SAT algorithms
Chair:
Location: FH, Seminarraum 101B
15:30 | Lower bounds for splittings by linear combinations (abstract) |
16:00-16:30Coffee Break
16:30-17:30 Session 34M: Contributed Talks: Proof Complexity
Chair:
Location: FH, Seminarraum 101B
16:30 | Narrow Proofs May Be Maximally Long (abstract) |
17:00 | Parity games and propositional proofs (abstract) |