Computer Sciences Colloquium - DESCRIPTIVE COMPLEXITY: USING LOGIC TO UNDERSTAND COMPUTATION

Neil Immerman - Lecturer, Mortimer & Raymond Sackler Institute of Advanced Studies

14 May 2017, 11:00 
Schreiber Building, Room 006 
Computer Sciences Colloquium

Abstract

 

Most computational problems can be understood as computing a function from n-bit inputs to m-bit outputs. The bits of the output are properties of the input. It is striking that the computational complexity of computing the function in terms of time, space, number of processors, etc., can be completely understood via the expressive power of the logical language needed to describe these properties. This will be an accessible talk explaining descriptive complexity and the resulting insights gained. I will end by describing some of the progress achieved by many researchers over the last 5 years.

 
 
Tel Aviv University makes every effort to respect copyright. If you own copyright to the content contained
here and / or the use of such content is in your opinion infringing, Contact us as soon as possible >>