VSL 2014: VIENNA SUMMER OF LOGIC 2014

This page contains an index consisting of author-provided keywords.

A
automatizability	Parity games and propositional proofs
B
bounded arithmetic	Provably Total Search Problems in Fragments of Bounded Arithmetic Below Polynomial-time Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic Parity games and propositional proofs Parameter-free induction in bounded arithmetic
C
CDCL	Size-Space Bounds and Trade-offs for CDCL Proofs
Clause Learning	Size-Space Bounds and Trade-offs for CDCL Proofs
D
degree	Narrow Proofs May Be Maximally Long Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
DPLL	Lower bounds for splittings by linear combinations
F
formalization	Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
Frege systems	Quasipolynomial Size Frege Proofs of Frankl's Theorem on the Trace of Finite Sets
I
induction rule	Parameter-free induction in bounded arithmetic
K
k-fold Tseitin formula	Lower bounds for splittings by linear combinations
Kruskal-Katona Theorem	Quasipolynomial Size Frege Proofs of Frankl's Theorem on the Trace of Finite Sets
L
Lasserre	Narrow Proofs May Be Maximally Long
length	Narrow Proofs May Be Maximally Long Size-Space Bounds and Trade-offs for CDCL Proofs
lower bound	Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds Lower bounds for splittings by linear combinations
M
Monotone proofs	n^O(log log n) size monotone proofs of the weak pigeonhole principle
P
parameter-free induction	Parameter-free induction in bounded arithmetic
parity games	Parity games and propositional proofs
PCR	From Small Space to Small Width in Resolution Narrow Proofs May Be Maximally Long Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
pigeonhole principle	Quasipolynomial Size Frege Proofs of Frankl's Theorem on the Trace of Finite Sets Lower bounds for splittings by linear combinations
polynomial calculus	From Small Space to Small Width in Resolution Narrow Proofs May Be Maximally Long Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
proof complexity	From Small Space to Small Width in Resolution Narrow Proofs May Be Maximally Long Provably Total Search Problems in Fragments of Bounded Arithmetic Below Polynomial-time Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds Size-Space Bounds and Trade-offs for CDCL Proofs
pseudorandom constructions	Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
Q
Q-resolution	Beyond Q-Resolution and Prenex Form: A Proof System for Quantified Constraint Satisfaction
quantified constraint satisfaction	Beyond Q-Resolution and Prenex Form: A Proof System for Quantified Constraint Satisfaction
R
Random CNFs	Total Space in Resolution
rank	Narrow Proofs May Be Maximally Long
resolution	From Small Space to Small Width in Resolution Narrow Proofs May Be Maximally Long Size-Space Bounds and Trade-offs for CDCL Proofs Parity games and propositional proofs Lower bounds for splittings by linear combinations Total Space in Resolution
S
search problems	Provably Total Search Problems in Fragments of Bounded Arithmetic Below Polynomial-time
separation	Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
Sherali-Adams	Narrow Proofs May Be Maximally Long
size	Narrow Proofs May Be Maximally Long Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
space	From Small Space to Small Width in Resolution Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds Size-Space Bounds and Trade-offs for CDCL Proofs
T
the pcp theorem	Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
Total Space	Total Space in Resolution
tractability theory	Beyond Q-Resolution and Prenex Form: A Proof System for Quantified Constraint Satisfaction
U
upper bound	n^O(log log n) size monotone proofs of the weak pigeonhole principle
W
weak pigeonhole principle	n^O(log log n) size monotone proofs of the weak pigeonhole principle
width	From Small Space to Small Width in Resolution Narrow Proofs May Be Maximally Long

Disclaimer | Powered by EasyChair Smart Program