CS Theory/Math Seminar


Oganizer: Elena Grigorescu

Our seminar will meet sporadically this semester. Please check the calendar for the exact details. To get announcement before the talk, please also join our mailing list. You might also wish to sign up for the reading group.

Schedule, Spring 2015

Wednesday Jan 21

Dana Randall
Georgia Tech

CONTE DISTINGUISHED LECTURE. Title: Phase Transitions in Algorithms and Applications LWSN 1142, 3:30-4:30pm.

Abstract: Markov chain Monte Carlo methods have become ubiquitous across science and engineering as a means of exploring large configuration spaces. The idea is to walk among the configurations so that even though you explore a very small part of the space, samples will be drawn from a desirable distribution. Over the last 20 years there have been tremendous advances in the design and analysis of efficient sampling algorithms for this purpose, largely building on insights from statistical physics. One of the striking discoveries has been the realization that many natural Markov chains undergo a phase transition where they change from begin efficient to inefficient as some parameter of the system is modified. In this talk we will explore this phenomenon, and show how insights from computing reveal interesting results in other fields, including colloids, models of segregation, and packing problems from discrete mathematics.

BIO: Dana Randall is Director of the Algorithms and Randomness Center at Georgia Tech, where she is the Advance Professor of Computing and an Adjunct Professor of Mathematics. Dr. Randall is a Fellow of the American Mathematical Society, a National Associate of the National Academies, and a former recipient of a Sloan Fellowship and an NSF Career Award. She holds degrees in Computer Science and Mathematics from Harvard University and U.C. Berkeley. Her research on randomized algorithms and sampling has helped create an interdisciplinary field bridging computer science, discrete probability and statistical physics.

Wed Feb 4

Bimal K. Roy
Director, Indian Statistical Institute

Time/Location: TBD Title: Combinatorial Batch Codes

Abstract: Initiated by Ishai, Kushilevitz, Ostrovsky, and Sahai, combinatorial batch codes (CBCs) refer to efficient retrieval of data items from a database with appropriate security constraints. Thus, there are n data items, which are stored in m servers, with duplications allowed, and N is the total storage. For any given k, some k items are to be retrived under the constraint that at most t (t <= k) items can be retrived from any single server. The mathematical problem is to minimize N, for given n,m,k,t. Followed by a review, new results on construction of optimal CBCs are presented. The problem arises naturally in cryptography.

BIO: Bimal K. Roy is Director, Indian Statistical Institute and a Fellow of the National Academy of Sciences, India. He has published numerous articles in a wide variety of areas in computer science, combinatorics and cryptography, statistical design, statistical ecology, and sensor networks. He is a recipient of the Reliance-NASI Platinum Jubilee Award in Physical Sciences and the IBM Award in Cryptology annd Security. Professor Roy has held visting positions in Waterloo, Ottawa, INRIA-Paris, Japan, and the Chinese Academy of Sciences. He has supervised the PhD theses of numerous students on combinatorics and design, statistical cryptography and sensor networks.

Link to schedule for Fall 2014. Spring 2014, Fall 2013. Spring 2013. Fall 2012. <html>