• Sep

    Time: 11:00am

    Location: Kharazmi Hall, CE Department, 4th Floor




    Title: Algorithm Design with Knowledge: Secretaries and Prophets


    In this talk, we consider more efficient algorithm design when wehave some knowledge about the input instance. Knowledge such asstructure of the input or input distributions can be used to designmore efficient algorithms especially for practical scenarios. Thisis in contrast to the worst case analysis that hardly may happen inreal-world. To give examples of such algorithms, in particular we consider twopopular versions of online selection problems – secretary problemsand prophet inequalities. In both of these problems, elements of aset are revealed one at a time and we have some knowledge about thedistribution of the input. When an element is revealed, we  mustimmediately and irrevocably decide whether to accept, but forgoingthe opportunity to see the remaining elements, or reject, bypassingthe element forever (but we still see future elements). We coverseveral extensions of these popular online selection problems incomputer science which are mainly followups of two pioneering worksof the speaker.


    Mohammad Hajiaghayi is the Jack and Rita G. Minker Professor in Computer Science Department at the University of Maryland, College Park. He is also Affiliate Professor in the Decision, Operations, and Information Technologies Area of the University of Maryland Robert H. Smith School of Business.  His main area of research is designing algorithmic frameworks for complex networked systems. In particular, he designs efficient approximation algorithms, fixed-parameter algorithms, game theory algorithms, and streaming algorithms for big and complex networks, and often tests them in real-world and practical situations. He is a recipient of the European Association for Theoretical Computer Science (EATCS) Nerode Prize (2015), University of Maryland Graduate Mentor of the Year Award (2015), ONR Young Investigator Award (2011), NSF CAREER Award (2010), and Google Faculty Research Award (2010 & 2014), and a few other grants. In the course of his professional career, he has published over 200 papers with over 190 co-authors, received a few best paper awards, and served on program committees or editorial boards of several well-known international computer science conferences and journals. In particular he was/is the program committee chair for IFIP TTCS’15 as well as ACM SPAA’17.  He has 10 granted and 2 filed US patents and has given over 60 invited talks around the world, and organized several workshops and tutorials. Last but not least he holds Silver Medal in 9th International Olympiad in Informatics (IOI’97) and awarded the best undergraduate prize of Sharif CE department in 2000 (for his highest GPA).