BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260416T202942Z
UID:Seminar-dept-1058@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20230629T130000
DTEND:20230629T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Nikhil Balaji: Testing Equality of Compressed Strings in Randomised NC\n\nThere has been extensive work on the problem of testing equality of compressed strings represented via straight-line programs. Efficient algorithms for the problem have been known since the work of Hirschfield et al., Plandowski, Melhorn et al. (1994), Je\.{z} (2012). There are also randomized algorithms known (Gasieniec et al., Schmidt-Schauß and Schnitger); however none of these algorithms are known to be parallelizable and it is open whether the question of testing compressed string equality is P-complete. \n\n\n\nKönig and Lohrey showed that the problem admits a RNC algorithm by reduction to the polynomial identity testing problem. We present a different RNC algorithm for this problem that is arguably simpler. Our algorithm is based on the cyclotomic identity testing (CIT) problem: given a polynomial f(x_1,…,x_k), decide whether f(ζ_n^{e_1},…, ζ_n^{e_k}) is zero, where ζ_n = e^{2\ π  i/n} is a primitive complex n-th root of unity and e_1,…,e_k are integers, represented in binary. \n\n\n\nBased on a joint work with Sylvain Perifel, Mahsa Shirmohammadi and James Worrell. \n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1058
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR