voula@utcsrgv.UUCP (Voula Vanneli) (02/11/85)
UNIVERSITY OF TORONTO
DEPARTMENT OF COMPUTER SCIENCE
(SF = Sandford Fleming Building, 10 King's College Road)
(MC = McLennan Physical Laboratories, 60 St. George Street)
(RS = Rosebrugh Building, Taddlecreek Road)
THEORETICAL ASPECTS SEMINAR - Monday, February 18, 11 a.m.,
SF 1101
Mr. Eric W. Allender
School of Information and Computer Science
Georgia Institute of Technology
"Uniformity in Parallel Algorithms"
UNIVERSITY OF TORONTO
DEPARTMENT OF COMPUTER SCIENCE
(SF = Sandford Fleming Building, 10 King's College Road)
(MC = McLennan Physical Laboratories, 60 St. George Street)
(RS = Rosebrugh Building, Taddlecreek Road)
THEORETICAL ASPECTS SEMINAR - Thursday, February 21, 3 p.m.,
SF 1105
Mr. Samuel R. Buss
Mathematics Department, Princeton
"The Polynomial Time Hierarchy and Fragments of Bounded Arithmetic"
UNIVERSITY OF TORONTO
DEPARTMENT OF COMPUTER SCIENCE
(SF = Sandford Fleming Building, 10 King's College Road)
(MC = McLennan Physical Laboratories, 60 St. George Street)
(RS = Rosebrugh Building, Taddlecreek Road)
THEORETICAL ASPECTS SEMINAR - Friday, February 22, 10 a.m.,
MC 252
Dr. Amos Israeli
Computer Science Department
Technion, Haifa
"A Fast and Simple Randomized Parallel Algorithm for Maximal Matching" *
A parallel randomized algorithm to find a maximal
matching is presented. Its expected running time on a
CRCW-PRAM with |_E| processors is 0(_l_o_g|_E|). The expected
time is independent of the structure of the input graph.
This improves the best known deterministic algorithm by a
factor of log829|_E|.