PC 2014 ABSTRACTS: KEYWORD INDEX

Papers Papers with Abstracts Preface Author Index Keyword Index

Shortcuts: A B C D F I K L M P Q R S T U W

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