Expansions of pseudofinite structures and circuit and proof complexity

Abstract

I shall describe a general model-theoretic task to construct expansions of pseudofinite structures and discuss several examples of a particular relevance to computational complexity.

Keywords

• Expansions
• pseudofinite
• structures
• circuit
• proof
• complexity