VSL 2014: VIENNA SUMMER OF LOGIC 2014
LCC ON SUNDAY, JULY 13TH, 2014
Days:
previous day
all days

View: session overviewtalk overviewside by side with other conferences

09:00-10:15 Session 23F: ImmermanFest Opening and Invited Talk
Location: FH, Zeichensaal 3
09:00
ImmermanFest Opening Remarks
09:15
27 and still counting: Iterated product, inductive counting, and the structure of P
SPEAKER: Eric Allender

ABSTRACT. This month marks an important anniversary.  It was precisely 33 years ago (July, 1987) that Neil Immerman announced a proof that NL = coNL. This shook the complexity-theoretic universe, triggering the collapse of multiple hierarchies, and spawning a series of aftershocks that still reverberate. This lecture will survey some of these developments, and will also trace the impact of some work of Immerman and Landau, which brought to the fore the central role that is played by iterated multiplication (in different algebras), in elucidating the structure of subclasses of P.

10:15-10:45Coffee Break
10:45-12:45 Session 26A: Invited Talks
Location: FH, Zeichensaal 3
10:45
Some Reflections on Definability and Complexity
11:45
Crane Beach Revisited
13:00-14:30Lunch Break
14:00-16:00 Session 30: Invited Talks
Location: FH, Zeichensaal 3
14:00
On the power of fixed-point logic with counting
SPEAKER: Anuj Dawar

ABSTRACT. In 1982, Neil Immerman proposed an extension of fixed-point logic by means of counting quantifiers (which we denote FPC) as a logic that
might express all polynomial-time properties of unordered structures.  It was eventually proved (by Cai, Fürer and Immerman) that there are
polynomial-time graph properties that are not expressible in FPC. Nonetheless, FPC is a powerful and natural fragment of the complexity class P.  In this talk, I will demonstrate this point by reviewing three recent results on the expressive power of FPC.

 

15:00
Reasoning about transitive closure in Immerman's style
SPEAKER: Mooly Sagiv
16:00-16:30Coffee Break
16:30-17:45 Session 34A: Invited Talk and Closing
Location: FH, Zeichensaal 3
16:30
The Variable Hierarchy on Ordered Graphs
17:30
Closing Remarks
SPEAKER: Neil Immerman