Speakers

Title: Online algorithms and other conceptually simple algorithms by

Speaker: Prof. Allan Borodin
University Professor at the University of Toronto, Canada

Abstract: What can and cannot be computed by “conceptually simple algorithms”? In this regard, my primary interest is on approximation algorithms for combinatorial optimization problems and the relation of such problems to areas such as algorithmic game theory and computational social choice. Why do we care about conceptual simplicity and can we formalize such a concept? For some problems, simple algorithmic ideas provide the best known solution or are reasonably competitive with the best known algorithms. Moreover, “in practice”, it is often the case that users will opt for a quick understandable algorithm. While it is arguably impossible to precisely define a useful general definition of “simplicity”, we can study well used (albeit rarely precisely defined) combinatorial algorithmic paradigms such as various forms and extensions of online and greedy algorithms, primal dual algorithms, and “simple” dynamic programming. We can provide definitions for such paradigms that are sufficiently expressive so as to capture many or most existing algorithms, but still allow us to prove impossibiity results that do not rely on computational complexity assumptions. More generally, in addition to competitive and approximation ratios for online and greedy algorithms, we are led to what might be called the price of simplicity for different objectives such as fairness or distortion in social choice applications.

Short Bio:Allan Borodin is a University Professor at the University of Toronto in the Department of Computer Science. He joined the University of Toronto in 1969 and was the chair of the Department 1980-1985. His research areas include computational complexity and algorithm analysis and design.

He has been a visiting professor at Cornell, ETH-Zurich, University of Nice, Hebrew University, and the Weizmann Institute. He is a Fellow of the Royal Society of Canada, an ACM Fellow and a Member, Order of Canada.

Title: AI-EDGE: Designing future XG Networks and Distributed intelligence

Speaker: Prof. Ness B Shroff
Chaired Professor of ECE and CSE, The Ohio State University, USA

Abstract: Networking and AI are two of the most transformative information technologies. These technologies have helped improve the quality of the human condition, contributed to national economic competitiveness, national security, and national defense. The AI-EDGE Institute is aimed at leveraging the synergie between both networking and AI to design the next generation of edge network. A new distributed intelligence plane will be developed to ensure that these networks are self-healing, adaptive, and self-optimized. The future of AI is distributed AI and these intelligent and adaptive networks will in turn unleash the power of collaboration to solve long-standing distributed AI challenges, making AI more efficient, interactive, and privacy preserving. The Institute plans to develop the key underlying technologies for distributed and networked intelligence to enable a host of future transformative applications such as intelligent transportation, remote healthcare, distributed robotics, and smart aerospace. Going beyond research, the Institute recognizes that it is a national priority to educate students, professionals, and practitioners in AI and networks, and substantially grow and diversify the workforce. The Institute will develop novel, efficient, and modular ways of creating and delivering education content and curricula at scale, and to spearhead a program that helps build a large diverse workforce in AI and networks spanning primary and secondary education to university students and faculty. In this talk, the speaker will first give an overview of the key research components of the Institute, identifying a set of research directions and open problems that may be of interest to the broader audience. The speaker will then describe through a case study involving edge-caching, why the edge is so different from the core of the network, and how Machine Learning (ML) tools and techniques can be developed to improve the performance in Edge Networks.

Biography: Ness B. Shroff received his Ph.D. degree from Columbia University, NY in 1994 and joined Purdue university immediately thereafter. At Purdue, he became Professor of the school of Electrical and Computer Engineering and director of CWSA in 2004, a university-wide center on wireless systems and applications. In July 2007, he joined the ECE and CSE departments at The Ohio State University, where he holds the Ohio Eminent Scholar Chaired Professorship of Networking and Communications. From 2009-2012, he also served as a Guest Chaired professor of Wireless Communications at Tsinghua University, Beijing, China, and an Honorary Guest Professor at Shanghai Jiatong University. He is a visiting professor at the Indian Institute of Technology, Bombay. He currently serves as the Principal Investigator and Institute Director of the NSF AI Institute on Future Edge Networks and Distributed Intelligence (ai-edge.osu.edu). Dr. Shroff’s research focuses on fundamental problems in machine learning, network optimization, stochastic control, and algorithmic design. Dr. Shroff is a Fellow of the IEEE, and a National Science Foundation CAREER awardee. He has received numerous best paper awards and has been on the list of highly cited researchers from Thomson Reuters ISI (previously ISI web of Science) in 2014 and 2015, and in Thomson Reuters Book on The World’s Most Influential Scientific Minds in 2014. He received the IEEE INFOCOM achievement award for seminal contributions to scheduling and resource allocation in wireless networks, in 2014.

Title: Concurrent Data Sketches

Speaker: Prof. Idit Keidar
Chaired Professor and the current Dean of the Viterbi Faculty of Electrical and Computer Engineering at the Technion – Israeli Institute of Technology

Abstract: Data sketching algorithms have become an indispensable tool for high-speed computations over massive datasets. They maintain a succinct summary of a data stream’s state and answer queries on it using limited memory, at the cost of giving approximations rather than exact answers. For example, a Θ sketch estimates the number of unique items in a data stream, the CountMin sketch approximates the frequencies at which distinct stream elements occur, and a Quantiles sketch estimates the data distribution of a large input stream.

This talk will discuss efficient concurrent (multi-threaded) implementations of such objects.We will first present an efficient generic approach to parallelizing data sketches and allowing them to be queried in real time, while bounding the error that such parallelism introduces. When instantiated with the KMV Θ sketch sketch, this solution achieves high scalability with a small error. Its implementation is now now publicly available as part of the popular Apache Data Sketches library.

Second, we will discuss the correctness semantics of such objects. We will define Intermediate Value Linearizability (IVL), a correctness criterion that relaxes linearizability to allow more parallelism, and yet preserves the error bounds of sequential (probabilistic) sketches. To illustrate the power of this result, we will show a straightforward and efficient concurrent implementation of a CountMin sketch, which is IVL (albeit not linearizable).

Finally, we will consider the Quantiles sketch, which does not scale well using the generic concurrent sketches approach. We instead present Quancurrent, a highly scalable quantiles sketch.

Based on joint works with Edward Bortnikov, Shaked Elias-Zada, Eshcar Hillel, Lee Rhodes, Arik Rinberg, Hadar Serviansky, and Alexander Spiegelman.

Biography: Idit Keidar is a Chaired Professor and the current Dean of the Viterbi Faculty of Electrical and Computer Engineering at the Technion – Israeli Institute of Technology. She received her BSc (summa cum laude), MSc (summa cum laude), and PhD from the Hebrew University of Jerusalem in 1992, 1994, and 1998, respectively. Subsequently, she was a Rothschild Postdoctoral Fellow at MIT’s Laboratory for Computer Science. She was a Visiting Professor at Cornell and has consulted for several companies. Prof. Keidar has also served as the program chair for leading conferences (PODC, DISC, PPoPP, and SYSTOR). In her free time, she enjoys writing prose.