Stephen Fenner, University of South Carolina Abstract: We show that the bipartite perfect matching problem is in quasi-NC. In particular, it has uniform circuits of quasi-polynomial size and O(log^2 n) depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the Isolation Lemma of Mulmuley, Vazirani, & Vazirani, which was used to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem. Time permitting, we describe an RNC algorithm to find a perfect matching in a bipartite graph using O(log^2 n) random bits. Bio: Stephen Fenner is a professor of Computer Science and Engineering at the University of South Carolina. His research interests are in theoretical computer science and include computational complexity, computability, algorithms, and quantum informatics. Be aware, this talk will be held in an earlier timeslot (1:45 - 3:00) in a different room (2A19) than usual. This seminar is open to anyone who is interested, not just students enrolled in the CSCE 791 class. Please consider attending.