Past event
Centre for Interdisciplinary Research in Computational Algebra (CIRCA) lunchtime seminar
There will be a Centre for Interdisciplinary Research in Computational Algebra (CIRCA) lunchtime seminar on Thursday 10th October at 1pm in Physics Lecture Theatre C.
Andras Salamon and Peiran Wu will speak at this CIRCA seminar, Andras on ‘A new time hierarchy theorem' and Peiran on ‘Irredundant bases for primitive wreath products'.
Andras' abstract: With Michael Wehar I have recently improved a result of Fortnow and Santhanam 2016, showing that when the amount of time allowed for a computation is increased more than logarithmically then new languages can be decided. Also extending the classical deterministic time hierarchy theorem (Hartmanis and Stearns 1965), such languages exist even in the presence of at most linearly many bits of nondeterminism. I will present the new difference gadget and contrast it with previous gadgets.
For more information about CIRCA and its activities, visit the CIRCA website.