In the recent years the field of sublinear algorithms has led to multiple exciting new theoretical developments in algorithms for massive data processing. The goal of this workshop is to discuss recent work and new challenges in sublinear algorithms and how they relate to Big Data and massively parallel computing. Among multiple research areas represented at this workshop primary focus will be given to algorithms for MapReduce, streaming, distributed machine learning, property testing and communication complexity. An in-depth coverage of these topics will be given through 5 invited keynotes and tutorials accompanied by 15-20 talks by the leading experts in the area with broad representation from both academia and industry. We highly encourage attendance by graduate students who will have an opportunity to showcase their work during a poster session.

  • When?
    August 27–28, 2015.
  • Where?
    DIMACS, located at CoRE building at Rutgers University. See information here for directions.
  • What?
    See the schedule and the list of speakers.
  • Poster session? We encourage the visitors (especially students and postdocs) to present a poster at the poster session that will take place in the evening of Day 1 (see schedule). Please, submit a title and a one-paragraph abstract of your poster by August 20 to Grigory Yaroslavtsev (grigory at In the title of your e-mail please include "DIMACS Poster: YOUR_NAME". Notifications of acceptance will be sent shortly after the deadline.
  • Do I need to register?
    Yes, registration is required. Note that in many cases the registration fee can be either reduced or waived. The early registration deadline is August 20.




Day 1, August 27

Day 2, August 28


Keynote Speakers

  • Ashish Goel (Stanford University)

    Ashish Goel is a Professor of Management Science and Engineering and (by courtesy) Computer Science at Stanford University, and a member of Stanford's Institute for Computational and Mathematical Engineering. He received his PhD in Computer Science from Stanford in 1999, and was an Assistant Professor of Computer Science at the University of Southern California from 1999 to 2002. His research interests lie in the design, analysis, and applications of algorithms; current application areas of interest include social networks, participatory democracy, Internet commerce, and large scale data processing. Professor Goel is a recipient of an Alfred P. Sloan faculty fellowship (2004-06), a Terman faculty fellowship from Stanford, an NSF Career Award (2002-07), and a Rajeev Motwani mentorship award (2010). He was a co-author on the paper that won the best paper award at WWW 2009, and an Edelman Laureate in 2014.

    Professor Goel was a research fellow and technical advisor at Twitter, Inc. from July 2009 to Aug 2014.

  • Piotr Indyk (Massachusetts Institute of Technology)

    Piotr joined MIT in September 2000, after earning PhD from Stanford University. Earlier, he received Magister degree from Uniwersytet Warszawski in 1995. As of July 2010, he holds the title of Professor in the Department of Electrical Engineering and Computer Science.

    Piotr's research interests include algorithms for high-dimensional geometric problems, algorithms using sublinear time and/or space and streaming algorithms.

  • John Langford (Microsoft Research, NYC)

    John Langford studied Physics and Computer Science at the California Institute of Technology, earning a double bachelor's degree in 1997, and received his Ph.D. from Carnegie Mellon University in 2002. Since then, he has worked at Yahoo!, Toyota Technological Institute, and IBM's Watson Research Center. He is also the primary author of the popular Machine Learning weblog, and the principle developer of Vowpal Wabbit. Previous research projects include Isomap, Captcha, Learning Reductions, Cover Trees, and Contextual Bandit learning. For more information visit his homepage.

Tutorial Speakers

  • Sergei Vassilvitskii (Google Research, NYC)

    Sergei Vassilvitskii is a Research Scientist at Google New York. Previously he was a Research Scientist at Yahoo! Research and an Adjunct Assistant Professor at Columbia University. He completed my PhD at Stanford Universty under the supervision of Rajeev Motwani. Prior to that he was an undergraduate at Cornell University.

  • David Woodruff (IBM Research, Almaden)

    David Woodruff is a Research Staff Member at IBM Research, Almaden. David did his Ph.D. at MIT in theoretical computer science. He was very fortunate to have Piotr Indyk as his advisor and to spend a year at Tsinghua University under the supervision of Andy Yao. His current interests are communication complexity, data stream algorithms and lower bounds, graph algorithms, machine learning, numerical linear algebra, sketching, and sparse recovery.

Regular Speakers

  • Nina Balcan (Carnegie Mellon University)

    Maria-Florina Balcan is an Associate Professor in the School of Computer Science at Carnegie Mellon University. Her main research interests are machine learning, computational aspects in economics and game theory, and algorithms. Her honors include the CMU SCS Distinguished Dissertation Award, an NSF CAREER Award, a Microsoft Faculty Research Fellowship, a Sloan Research Fellowship, and several paper awards. She was a Program Committee Co-chair for COLT 2014 , and is currently a board member of the International Machine Learning Society and a Program Committee Co-chair for ICML 2016.

  • Mark Braverman (Princeton University)

    Assistant Professor Mark Braverman joined the department in 2011 from the University of Toronto, where he was an assistant professor in the mathematics and computer science departments. He earned his Ph.D. in 2008 from Toronto and did post-doctoral research at Microsoft Research New England, Cambridge, MA. Professor Braverman’s interests center on the connections between theoretical computer science and other disciplines, including information theory, mathematics, and economics. Most recently, he has been building new connections between information theory and complexity theory, and investigating how better algorithms can lead to better mechanism design, particularly in the context of healthcare.

  • Amit Chakrabarti (Dartmouth College)

    Amit Chakrabarti is an Associate Professor in the Department of Computer Science at Dartmouth College. He received an M.A. and a Ph.D. in Computer Science from Princeton University in 2002 and a B.Tech. in Computer Science from the Indian Institute of Technology, Bombay, along with the President of India Gold Medal, in 1997. Professor Chakrabarti's research is in the broad area of theoretical computer science. Specific interests are (1) complexity theory, especially communication complexity and the application of information theory, and (2) algorithms, including space-efficient algorithms for massive data streams and approximation techniques for optimization problems.

  • Graham Cormode (University of Warwick)

    Graham Cormode is a professor in the Department of Computer Science at the University of Warwick in the UK. His interests are in data stream analysis, massive data sets, and general algorithmic problems. Previously, he has been a researcher at AT&T Labs–Research in New Jersey, and at Lucent Bell Laboratories, with focus on Network Management. Previously, he was a Postdoc researcher at the DIMACS research facility, which is located at Rutgers University.

  • Artur Czumaj (University of Warwick)

    Artur Czumaj is a Professor of Computer Science and Director of the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick. He received his Ph.D. in 1995 from the University of Paderborn in Germany. Before joining the University of Warwick in 2006, he was with the University of Paderborn and with the New Jersey Institute of Technology. His main research interest is in the broadly understood area of the design of randomized algorithms and their probabilistic analysis, with applications to property testing and sublinear algorithms, optimization algorithms, parallel and distributed computing, string matching, and algorithmic game theory.

  • Alina Ene (University of Warwick)

    Alina Ene is an Assistant Professor in the Department of Computer Science at the University of Warwick. Previously, she was a postdoc in the Center for Computational Intractability in Princeton. Her research interests include submodularity, graph algorithms including routing and network design, algorithms for massive data, and applications in machine learning and computer vision.

  • Funda Ergun (Indiana University, Bloomington & Simon Fraser University)

    Funda Ergun received her BS from Bilkent University in Ankara, Turkey and PhD from Cornell University. She is currently a professor of Computer Science at Indiana University and Simon Fraser University. Her interests lie in sublinear/streaming algorithms, as well as the algorithmic aspects of networking.

  • Sudipto Guha (University of Pennsylvania)

    Sudipto Guha is an Associate Professor in the Department of Computer and Information Sciences at University of Pennsylvania since Fall 2001. He completed his Ph.D. in 2000 at Stanford University working on approximation algorithms and spent a year working as a senior member of technical staff in Network Optimizations and Analysis Research department in AT&T Shannon Labs Research. He is a recipient of the NSF CAREER award and the Alfred P. Sloan Foundation fellowship.

  • Sanjeev Khanna (University of Pennsylvania)

    Sanjeev Khanna is a Henry Salvatori Professor of Computer and Information Science at University of Pennsylvania. He received a Ph.D. in Computer Science from Stanford University (1996), and undergraduate degrees in Computer Science and Economics from Birla Institute of Technology, India (1990). From 1996 to 1999, he was a member of the Mathematical Sciences Research center at Bell Labs. He joined University of Pennsylvania in 1999. Sanjeev's research interests are in algorithms and complexity with a focus on approximation algorithms and hardness of approximation. He is a recipient of an Arthur Samuel dissertation award, a Sloan Fellowship, and a Guggenheim Fellowship.

  • Silvio Lattanzi(Google Research, NYC)

    Silvio is a research scientist at Google New York. He received his PhD in Computer Science from Sapienza University of Rome under the supervision of Alessandro Panconesi. Silvio's research interests include efficient algorithms, social networks analysis and data mining.

  • Michael Mahoney (University of California, Berkeley)

    Michael Mahoney is in the Department of Statistics at the University of California, Berkeley. His research focuses on algorithmic and statistical aspects of modern large-scale data analysis and large-scale machine learning. Specific topics include randomized matrix algorithms and randomized numerical linear algebra, geometric network analysis tools for structure extraction in large informatics graphs, scalable implicit regularization methods, and applications in genetics, astronomy, medical imaging, social network analysis, and internet data analysis. He received his PhD from Yale University with a dissertation in computational statistical mechanics, and he has worked and taught at Yale University in the mathematics department, at Yahoo Research, and at Stanford University in the mathematics department. He served on the National Advisory Committee of the Statistical and Applied Mathematical Sciences Institute (SAMSI); he was on the National Research Council's Committee on the Analysis of Massive Data; he runs the biennial MMDS Workshops on Algorithms for Modern Massive Data Sets; and he spent fall 2013 at UC Berkeley co-organizing the Simons Foundation's program on the Theoretical Foundations of Big Data Analysis.

  • Andrew McGregor (University of Massachusetts, Amherst)

    Andrew McGregor is an Assistant Professor at the University of Massachusetts, Amherst. He received a B.A. degree and the Certificate of Advance Study in Mathematics from the University of Cambridge and a Ph.D. from the University of Pennsylvania. He also spent a couple of years as a post-doc at UC San Diego and Microsoft Research SVC. He is interested in many areas of theoretical computer science and specializes in data stream algorithms, linear sketching, and communication complexity. He received the NSF Career Award in 2010.

  • Vahab Mirrokni (Google Research, NYC)

    Vahab Mirrokni is a Senior Staff Research Scientist, heading the algorithms research group at Google Research, New York. He received his PhD from MIT in 2005 and his B.Sc. from Sharif University of Technology in 1999. He joined Google Research in New York in 2008, after spending a couple of years at Microsoft Research, MIT and He is the co-winner of a SODA05 best student paper award and ACM EC08 best paper award. His research areas include algorithms, algorithmic game theory, combinatorial optimization, and social networks analysis. At Google, he is mainly working on algorithmic and economic problems related to search and online advertising. Recently he is working on online ad allocation problems, distributed algorithms for large-scale graph mining, and mechanism design for advertising exchanges.

    Kamesh Munagala (Duke University)

    Kamesh Munagala is Associate Professor of Computer Science at Duke University, where he has been employed since 2004. He obtained his Ph.D. from Stanford University in 2003 and B.Tech. from IIT Bombay in 1998. He is broadly interested in algorithm design and discrete optimization. His work is both methodological, encompassing approximation algorithms, sequential decision theory, and algorithmic game theory, as well as applied to domains such as e-commerce, databases, data analysis, and networks. He is also interested in developing and analyzing models for complex internet systems. He is a recipient of the NSF CAREER Award, the Alfred P. Sloan Research Fellowship, and the best paper award at the WWW 2009 conference. He was a Visiting Research Professor at Twitter, Inc in 2012, and currently serves as the Director of Graduate Studies for the Duke CS department.

  • Jelani Nelson (Harvard University)

    Jelani Nelson is an Assistant Professor of Computer Science at Harvard University. His research interests include streaming algorithms, dimensionality reduction, compressed sensing, and large-scale linear algebra.

  • Krzysztof Onak (IBM T.J. Watson Research Center)

    Krzysztof Onak is a computer scientist who works at the IBM T.J. Watson Research Center near Yorktown Heights, NY. He is interested in computation with limited resources, including sublinear-time algorithms, streaming algorithms, and algorithms for modern parallel systems. Krzysztof received his Master's degree from the University of Warsaw and his PhD from the Massachusetts Institute of Technology. Before joining IBM, he was a Simons Postdoctoral Fellow at Carnegie Mellon University.

  • Ronitt Rubinfeld (Massachusetts Institute of Technology)

    Ronitt Rubinfeld received her PhD at the University of California, Berkeley, and is currently on the faculties at MIT and Tel Aviv University. Her research focuses on sub-linear time algorithms for big data sets.

  • Justin Thaler (Yahoo! Labs)

    Justin Thaler is a Research Scientist at Yahoo! Labs in New York. Previously, he spent two enjoyable semesters as a Research Fellow at the Simons Institute for the Theory of Computing at UC Berkeley. He received his Ph.D. from the Theory of Computation Group at Harvard University, where he was fortunate to be advised by Michael Mitzenmacher, and he graduated from Yale University in 2009 with a B.S. in Computer Science and a second major in Mathematics. He is broadly interested in algorithms and computational complexity, especially algorithms for massive data sets, verifiable computation, and computational learning theory.

Organizers and Support


  • Alexandr Andoni (Columbia University)

    Alexandr Andoni is an Associate Professor at Columbia University. He was previously a Researcher at Microsoft Research Silicon Valley. His research interests include sublinear algorithms, streaming, algorithms for massive data sets, high-dimensional computational geometry, metric embeddings and theoretical machine learning. Andoni graduated from MIT in 2009, under the supervision of Professor Piotr Indyk. His PhD thesis is entitled, "Nearest Neighbor Search: the Old, the New, and the Impossible." From 2009 to 2010, he was a postdoc at the Center for Computational Intractability at Princeton, and a visitor at NYU and IAS.

  • Muthu Muthukrishnan (Rutgers University)

    S. (Muthu) Muthukrishnan is a Professor of Computer Science at Rutgers University. His research interest is in Internet Auctions and Game Theory, as well as Data Stream Algorithms and its connections to Compressed Sensing, Databases and Networking. He also maintains a blog:

  • Grigory Yaroslavtsev (University of Pennsylvania)

    Grigory Yaroslavtsev is a postdoctoral fellow at the Warren Center for Network and Data Sciences at the University of Pennsylvania. He was previously a Postdoctoral Fellow in Mathematics at Brown University, ICERM. He received his Ph.D. in Theoretical Computer Science in 2013 from Pennsylvania State University and an M.Sc. in Applied Mathematics and Physics from the Academic University of the Russian Academy of Sciences in 2010. Grigory works on efficient algorithms for sparsification, summarization and testing properties of large data, including approximation, parallel and online algorithms, learning theory and property testing, communication and information complexity and private data release.


We gratefully acknowledge the support from DIMACS including the director Rebecca Wright, acting depty director Tami Carpenter, workshop coordinator Nicole Clark and publicity coordinator Linda Casals.