Verifying Proofs in Constant Depth
Professor Heribert Vollmer (University of Hanover)
Info
|
Date |
26th July 2011 (week , Trinity Term 2011) |
|
Time |
11:30 |
|
Place |
Wolfson Building, Room 147 |
Abstract
The seminar will begin with a short introduction into the field of proof complexity. Following this, Professor Vollmer will turn to the study of provers of very low complexity, i.e. computable by Boolean circuit families of small size and very small depth (log log n or constant).
He will investigate the question of which languages admit proof systems in this very restricted model. Both positive results, e.g., we present a constant-depth proof system for some NP-complete language, as well as negative results, e.g., we show that very simple even regularlanguage such as Exact-OR do not admit constant depth proof systems can be obtained and will be discussed.
Further info
|
Related series |
|
