Monday, February 26

3108 Etcheverry Hall

3:30 p.m. - 5:00 p.m.

Abstract: One of the greatest successes of computational complexity theory is the classification of countless fundamental computational problems into polynomial-time and NP-hard ones, two classes that are often referred to as tractable and intractable, respectively. However, this crude distinction of algorithmic efficiency is clearly insufficient when handling today's large scale of data. We need a finer-grained design and analysis of algorithms that pinpoints the exact exponent of polynomial running time, and a better understanding of when a speed-up is not possible. Over the years, many polynomial-time approximation algorithms were devised as an approach to bypass the NP-hardness obstacle of many discrete optimization problems. This area has developed into a rich field producing many algorithmic ideas and has lead to major advances in computational complexity. So far, however, a similar theory for high polynomial time problems to understand the trade-off between quality and running time is vastly lacking. 

In this presentation, I will give you an overview of the newly growing field of fine-grained algorithms and complexity, and my contributions therein. This will include fundamental problems such as edit distance computation, all-pairs shortest paths, parsing and matrix multiplication. They have applications ranging from genomics to statistical natural language processing, machine learning and optimization. I will show how as a natural byproduct of improved time complexity, one may design algorithms that are highly parallel as well as streaming algorithms with sublinear space complexity. Finally, motivated by core machine learning applications, I will discuss alternative measures of efficiency that may be equally relevant as time complexity.

Bio: Barna Saha is currently an Assistant Professor in the College of Information & Computer Science at the University of Massachusetts Amherst. She is also a Permanent Member of Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers. Before joining UMass in 2014, she was a Research Scientist at AT&T Shannon Laboratories, New Jersey. She spent four wonderful years (2007-2011) at the University of Maryland College Park from where she received her Ph.D. in Computer Science. In Fall 2015, she was at the University of California Berkeley as a Visiting Scholar and as a fellow of the Simons Institute. Her research interests include Theoretical Computer Science, Probabilistic Method & Randomized Algorithms and Large Scale Data Analytics. She is the recipient of NSF CAREER award (2017), Google Faculty Award (2016), Yahoo Academic Career Enhancement Award (2015), Simons-Berkeley Research Fellowship (2015), NSF CRII Award (2015) and Dean's Dissertation Fellowship (2011). She received the best paper award at the Very Large Data Bases Conference (VLDB) 2009 for her work on Probabilistic Databases and was chosen as finalists for best papers at the IEEE Conference on Data Engineering (ICDE) 2012 for developing new techniques to handle low quality data.

 

    Monday, April 2

    3108 Etcheverry Hall

    3:30 p.m. - 5:00 p.m.

    Agostino Capponi joined Columbia University's IEOR Department in August 2014, where he is also a member of the Institute for Data Science and Engineering.

    His main research interests are in the area of networks, with a special focus on systemic risk, contagion, and control. In the context of financial networks, the outcome of his research contributes to a better understanding of risk management practices, and to assess the impact of regulatory policies aimed at controlling financial markets. He has been awarded a grant from the Institute for New Economic Thinking for his research on dynamic contagion mechanisms.

    His research has been published in top-tier journals of Operations Research, Mathematical Finance, and Financial Economics, including Operations Research, Mathematics of Operations Research, Management Science, Review of Asset Pricing Studies, and Mathematical Finance. His work has also been published in leading practitioner journals and invited book chapters. Agostino is a frequently invited speaker at major conferences in the area of systemic risk. He has on-going collaborations with several governmental institutions that are tasked with the analysis of financial networks data, in particular the US Commodity Futures Trading Commission and the Office of Financial Research. Agostino holds a world patent for a target tracking methodology in military networks.

    Agostino received his Master and Ph.D. Degree in Computer Science and Applied and Computational Mathematics from the California Institute of Technology, respectively in 2006 and 2009.

    Monday, April 9

    3108 Etcheverry Hall

    3:30 p.m. - 5:00 p.m.

    Research: Max Shen is a professor at UC Berkeley in the Industrial Engineering and Operations Research Department. He researches supply chain design, design of optimization algorithms, energy systems optimation, and transportation system planning among other strategies.

    He currently works on the following projects:

    1. Projects funded by National Science Foundation
    2. Energy Management Systems for Smart Grid Users with Flexible Demand (Siemens)

    3. Towards a Green Supply Chain. Life Cycle Implications of Shipping Goods to California from Mexico vs. China (Blum Center)

    4. California Department of Transportation

     

    Monday, April 23

    3108 Etcheverry Hall

    3:30 p.m. - 5:00 p.m.

    Research: The primary focus of Professor David Schmoy's research is on the design and analysis of efficient algorithms for discrete optimization problems, and in particular, on approximation algorithms for NP-hard and other computationally intractable problems. Linear programming relaxations have played a fundamental role in obtaining good solutions to hard optimization problems, and he continue to study their application to a range of problems in clustering, sequencing and scheduling, and inventory problems, in both deterministic and stochastic optimization settings. In addition to studying these problems with a theoretical lens, he has been involved in the practical application of these techniques in settings ranging from genomics to medical aircraft scheduling to the long-term planning for the preservation of the red-cockaded woodpecker to the operational logistics and design of bike-sharing systems.

    Monday, April 30

    3108 Etcheverry Hall

    3:30 p.m. - 5:00 p.m.

    Professor Avraham Shtub holds the Stephen and Sharon Seiden Chair in Project Management. He has a B.Sc in Electrical Engineering from the Technion - Israel Institute of Technology (1974), an MBA from Tel Aviv University (1978) and a Ph.D in Management Science and Industrial Engineering from the University of Washington (1982).  He is a certified Project Management Professional (PMP) and a member of the Project Management Institute (PMI-USA).

    Professor Shtub is the recipient of the Institute of Industrial Engineering's 1995 "Book of the Year Award" for his Book "Project Management: Engineering, Technology and Implementation" (co- authored with Jonathan Bard and Shlomo Globerson), Prentice Hall, 1994. He is the recipient of the Production Operations Management Society's Wick Skinner Teaching Innovation Achievements Award for his book: "Enterprise Resource Planning (ERP): The Dynamics of Operations Management". His books on Project Management were published in English, Hebrew, Greek and Chinese. He is the recipient of the 2008 Project Management Institute Professional Development Product of the Year Award for the training simulator "Project Team Builder – PTB". Prof. Shtub was a Department Editor for IIE Transactions he was on the Editorial Boards of the Project Management Journal, The International Journal of Project Management, IIE Transactions and the International Journal of Production Research.

    He was a faculty member of the department of Industrial Engineering at Tel Aviv University from 1984 to 1998 where he also served as a chairman of the department (1993-1996). He joined the Technion in 1998 and was the Associate Dean and head of the MBA program.  He has been a consultant to industry in the areas of project management, training by simulators and the design of production-operation systems. He was invited to speak at special seminars on Project Management and Operations in Europe, the Far East, North America, South America and Australia. Professor Shtub visited and taught at Vanderbilt University, The University of Pennsylvania, Korean Institute of Technology, Bilkent University in Turkey, Otego University in New Zealand, Yale University, Universidad Politécnica de Valencia, University of Bergamo in Italy.