VSL 2014: VIENNA SUMMER OF LOGIC 2014
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)
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
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)
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
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
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
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)
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
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)
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
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
Location: FH, Seminarraum 101B
16:30
Narrow Proofs May Be Maximally Long (abstract)
17:00
Parity games and propositional proofs (abstract)