קולוקוויום בביה"ס למדעי המחשב - DESCRIPTIVE COMPLEXITY: USING LOGIC TO UNDERSTAND COMPUTATION
מרצה המכון ללימודים מתקדמים ע"ש מורטימר וריימונד סאקלר Neil Immerman
14 במאי 2017, 11:00
בניין שרייבר, חדר 006
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.