Department of Computer Science
April '21: ICALP 2021 papers on sparsification of directed graphs and universal algorithms for clustering.
February '21: STOC 2021 papers on Gomory-Hu trees and vertex connectivity.
December '20: We have multiple postdoctoral openings in the theory group for positions starting Summer/Fall 2021. In particular, I am looking for a postdoc in either graph algorithms or in the general area of algorithms under uncertainty. See my Research page for more details about these areas. Apply here for this position. Please send me an email note after applying if you specifically want to work with me. For a full consideration, please apply by January 31, although we are going to continue considering applications until the positions are filled.
September '20: SODA 2021 paper on combinatorial auctions in online settings.
September '20: VLDB 2021 paper on deletion propagation in databases.
July '20: FOCS 2020 paper on deterministic algorithm for minimum cut.
February '20: STOC 2020 paper on online caching with time windows.
I am an Associate Professor of Computer Science at Duke University. Before coming to Duke in 2013, I spent one year as a postdoctoral research in the theory group at Microsoft Research Redmond, where I did research in algorithms. In 2012, I obtained my PhD in theoretical computer science at MIT under the supervision of Prof. David Karger by defending this. Before coming to MIT, I worked at Bell Labs in Bangalore for a year, where I did research on algorithms and networks. I obtained my bachelors' and masters' degrees in Computer Science and Engineering at Jadavpur University, Kolkata in 2004 and IISc, Bangalore in 2006 respectively. At IISc, I did research in algorithms under the supervision of Prof. Ramesh Hariharan. A long time ago, I grew up in the industrial town of Durgapur where I went to St. Xavier's School.
My CV is available here.
My research is in Theoretical Computer Science, focusing on the Design and Analysis of Algorithms with provable properties. Specific topics of interest include:
Graph Algorithms, particularly the study of Cuts, Flows, and Connectivity in graphs.
Algorithms under Uncertainty, particularly Online Algorithms.
Theoretical Machine Learning, particularly its role in Beyond Worst-Case algorithm design.
Approximation Algorithms for Combinatorial Optimization of NP-hard problems.
Algorithms in the Real World, including algorithms for Online Search, Advertising, and E-commerce, in Computer, Social, and Information Networks, in Computational Economics, in Big Data environments and Database Systems, etc.
I am generally excited by any algorithms research problem, but for a sample of my current research directions, see here.
I am part of the theory group and am also affiliated/collaborate with the CS-econ, AI/ML, and database groups at Duke.
I currently have openings for postdocs, graduate students, and undergraduates. Please see here for details.
Ruoxu Cen (1st year PhD student)
Kevin Sun (3rd year PhD student)
To see the list of former students and postdocs, please click here.
My research has been funded by the National Science Foundation through various grants (including a CAREER Award), by faculty research awards from Google and Yahoo!, by the Indo-US Science and Technology Forum, and by Duke University. I gratefully acknowledge their support.
For more information about my funding, including current grants, please click here.
AWARDS & HONORS
I have been fortunate to have received several awards and honors, some of which are listed below:
NSF CAREER Award.
Selected as a top 5% instructor based on teaching evaluations in the Trinity College of Arts and Sciences, Duke University on multiple occasions.
Faculty research awards from Google and Yahoo!
Best Paper Award at SPAA.
MIT Presidential Fellowship.
Gold medals for ranking 1st in masters at IISc and undergraduate at Jadavpur University.
Jagadis Bose National Science Talent Search (JBNSTS) Scholarship.
National Talent Search Examination (NTSE) Scholarship awarded by Govt of India.
For a more complete list of awards and honors, please see my CV.
I have taught various courses in algorithms and theoretical computer science at the graduate and undergraduate levels.
Spring 2021. COMPSCI 330 Design and Analysis of Algorithms (undergraduate course in algorithms, will be co-taught with Prof. Rong Ge)
Spring 2021. COMPSCI 590.04 Special Topics in Computer Science: Machine Learning Algorithms (graduate course on "algorithms for ML" and "ML-augmented algorithms", will be co-taught with Prof. Rong Ge)
Fall 2021. COMPSCI 290 Special Topics: Great Ideas in Computer Science (an introduction to computer science from the perspective of the big ideas, conflicts, and questions that computer science has brought to the fore: the course will include discussions on the historical perspective of the emergence of computer science and its meteoric rise in less than a century, how computer science relates to mathematics, engineering, and other branches of science, the role of computer science in shaping human thought and knowledge in a modern world, and some of the big futuristic questions that computer science faces today in theory and practice)
For a complete list of the courses that I have taught (including links to course material), please click here.
I have served on various program committees, panels, juries, etc. Some of these are listed below. For a more complete list, please see my CV.
Selected Program Committees
32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021.
60th IEEE Symposium on Foundations of Computer Science (FOCS), 2019.
47th ACM Symposium on Theory of Computing (STOC), 2016.
26th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.
Duke University, Campus Box 90129
308 Research Drive (LSRC Building), Room D203
Durham, NC 27708 USA
Tel: +1 (919) 660-6545
Fax: +1 (919) 660-6519
The fastest and preferred way to reach me is by email. My username is my first name and the domain is cs.duke.edu