Most of this blog is about Theoretical Computer Science. What’s theoretical about computers? Well, there are a lot of questions related to algorithms and computation that are studied from a mathematical point of view. Indeed the first notion of computers and computation has been developed by a mathematician, Alan Turing, even before the birth of actual computers.
The focus of this blog is Propositional Proof Complexity, but I’ll happily wander around to other topics of Computational Complexity and Theoretical Computer Science. For further information about what Proof Complexity is I suggest the following surveys:
- Nathan Segerlind: The Complexity of Propositional Proofs. This is the most recent survey on propositional proof complexity, and gives a general view of the area.
- Paul Beame and Toniann Pitassi: Propositional Proof Complexity: Past, Present and Future. One of the classic surveys on proof complexity, but a little bit dated.
- Samuel R. Buss: Towards NP–P via Proof Complexity and Search. A survey on the relation between proof complexity and search problems.
- Jakob Nordström: Pebble Games, Proof Complexity, and Time-Space Trade-offs. A survey focused on the issue of how much memory usage in proofs and SAT-solving.
Blog’s official languages are English and Italian. I will use the latter mainly for expository articles devoted to non-academic audience.
I am Massimo Lauria, born and raised in Rome, Italy. Currently I am a PostDoc at the School of Computer Science and Communication of KTH Royal Institute of Technology, working in the research group of Jakob Nordström. Of course the views expressed in this blog are personal and are not necessarily shared by any member of KTH.