Speaker:
Prof. Tsung-yi HO
Professor
Department of Computer Science
National Tsing Hua University

 
Abstract:
Advances in microfluidic technologies have led to the emergence of biochip devices for automating laboratory procedures in biochemistry and molecular biology. Corresponding systems are revolutionizing a diverse range of applications, e.g., point-of-care clinical diagnostics, drug discovery, and DNA sequencing–with an increasing market. However, continued growth (and larger revenues resulting from technology adoption by pharmaceutical and healthcare companies) depends on advances in chip integration and design-automation tools. Thus, there is a need to deliver the same level of design automation support to the biochip designer that the semiconductor industry now takes for granted. In particular, the design of efficient design automation algorithms for implementing biochemistry protocols to ensure that biochips are as versatile as the macro-labs that they are intended to replace. This talk will first describe technology platforms for accomplishing “biochemistry on a chip”, and introduce the audience to both the droplet-based “digital” microfluidics based on electrowetting actuation and flow-based “continuous” microfluidics based on microvalve technology. Next, system-level synthesis includes operation scheduling and resource binding algorithms, physical-level synthesis includes placement and routing optimizations, and control synthesis and sensor feedback-based cyberphysical adaptation will be presented. In this way, the audience will see how a “biochip compiler” can translate protocol descriptions provided by an end user (e.g., a chemist or a nurse at a doctor’s clinic) to a set of optimized and executable fluidic instructions that will run on the underlying microfluidic platform. Finally, recent advances in open-source microfluidic ecosystem will be covered.

 
Biography:
Tsung-Yi Ho received his Ph.D. in Electrical Engineering from National Taiwan University in 2005. He is a Professor with the Department of Computer Science of National Tsing Hua University, Hsinchu, Taiwan. His research interests include several areas of computing and emerging technologies, especially in design automation of microfluidic biochips. He has been the recipient of the Invitational Fellowship of the Japan Society for the Promotion of Science (JSPS), the Humboldt Research Fellowship by the Alexander von Humboldt Foundation, the Hans Fischer Fellowship by the Institute of Advanced Study of the Technische Universität München, and the International Visiting Research Scholarship by the Peter Wall Institute of Advanced Study of the University of British Columbia. He was a recipient of the Best Paper Awards at the VLSI Test Symposium (VTS) in 2013 and IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems in 2015. He served as a Distinguished Visitor of the IEEE Computer Society for 2013-2015, a Distinguished Lecturer of the IEEE Circuits and Systems Society for 2016-2017, the Chair of the IEEE Computer Society Tainan Chapter for 2013-2015, and the Chair of the ACM SIGDA Taiwan Chapter for 2014-2015. Currently, he serves as the Program Director of both EDA and AI Research Programs of Ministry of Science and Technology in Taiwan, the VP Technical Activities of IEEE CEDA, an ACM Distinguished Speaker, and an Associate Editor of the ACM Journal on Emerging Technologies in Computing Systems, ACM Transactions on Design Automation of Electronic Systems, ACM Transactions on Embedded Computing Systems, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, and IEEE Transactions on Very Large Scale Integration Systems, a Guest Editor of IEEE Design & Test of Computers, and the Technical Program Committees of major conferences, including DAC, ICCAD, DATE, ASP-DAC, ISPD, ICCD, etc. He is a Distinguished Member of ACM.

 
Join Zoom Meeting:
https://cuhk.zoom.us/j/94385618900
https://cuhk.zoom.com.cn/j/94385618900(Mainland China)

 
Enquiries: Miss Caroline Tai at Tel. 3943 8440
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar-archive/

Speaker:
Mr. Yu LI
PhD student
King Abdullah University of Science & Technology (KAUST)

 
Abstract:
Biomolecules, existing in high-order structural forms, are indispensable for the normal functioning of our bodies. To demystify those critical biological processes, we need to investigate biomolecular structures and functions. In this talk, we showcase our efforts in that research direction using deep learning. First, we proposed a deep learning guarded Bayesian inference framework for reconstructing super-resolved structure images from the super-resolved fluorescence microscopy data. This framework enables us to observe the overall biomolecular structures in living cells with super-resolution in almost real-time. Then, we zoom in on a particular biomolecule, RNA, predicting its secondary structure. For this one of the oldest problems in bioinformatics, we proposed an unrolled deep learning method, which can bring us with 20% performance improvement, regarding the F1 score. Finally, by leveraging the physiochemical features and deep learning, we proposed the first-of-its-kind framework to investigate the interaction between RNA and RNA-binding proteins (RBP). This framework can provide us with both the interaction details and high-throughput binding prediction results. Extensive in vitro and in vivo biological experiments demonstrate the effectiveness of the proposed method.

 
Biography:
Yu Li is a PhD student at KAUST in Saudi Arabia, majoring in Computer Science, under the supervision of Prof. Xin Gao. He is a member of Computational Bioscience Research Center (CBRC) at KAUST. His main research interest is developing novel and new machine learning methods, mainly deep learning methods, for solving the computational problems in biology and understanding the principles behind the bio-world. He obtained MS degree in CS from KAUST at 2016. Before that, he got the Bachelor degree in Biosciences from University of Science and Technology of China (USTC).

 
Join Zoom Meeting:
https://cuhk.zoom.us/j/91295938758
https://cuhk.zoom.com.cn/j/91295938758(Mainland China)

 
Enquiries: Miss Caroline Tai at Tel. 3943 8440
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar-archive/

Speaker:
Mr. Di WANG
PhD student
State University of New York
Buffalo

 
Abstract:
Recent research showed that most of the existing learning models are vulnerable to various privacy attacks. Thus, a major challenge facing the machine learning community is how to learn effectively from sensitive data. An effective way for this problem is to enforce differential privacy during the learning process. As a rigorous scheme for privacy preserving, Differential Privacy (DP) has now become a standard for private data analysis. Despite its rapid development in theory, DP’s adoption to the machine learning community remains slow due to various challenges from the data, the privacy models and the learning tasks. In this talk, I will use the Empirical Risk Minimization (ERM) problem as an example and show how to overcome these challenges. Particularly, I will first talk about how to overcome the high dimensionality challenge from the data for Sparse Linear Regression in the local DP (LDP) model. Then, I will discuss the challenge from the non-interactive LDP model and show a series of results to reduce the exponential sample complexity of ERM. Next, I will present techniques on achieving DP for ERM with non-convex loss functions. Finally, I will discuss some future research along these directions.

 
Biography:
Di Wang is currently a PhD student in the Department of Computer Science and Engineering at the State University of New York (SUNY) at Buffalo. Before that, he obtained his BS and MS degrees in mathematics from Shandong University and the University of Western Ontario, respectively. During his PhD studies, he has been invited as a visiting student to the University of California, Berkeley, Harvard University, and Boston University. His research areas include differentially private machine learning, adversarial machine learning, interpretable machine learning, robust estimation and optimization. He has received the SEAS Dean’s Graduate Achievement Award and the Best CSE Graduate Research Award from SUNY Buffalo.

 
Join Zoom Meeting:
https://cuhk.zoom.us/j/98545048742
https://cuhk.zoom.com.cn/j/98545048742(Mainland China)
Meeting ID: 985 4504 8742

 
Enquiries: Miss Caroline Tai at Tel. 3943 8440
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar-archive/

Speaker:
Mr. Di JIN
PhD student
MIT

 
Abstract:
Deep learning models have been increasingly prevailing in various Natural Language Processing (NLP) tasks, and even surpassed human-level performance in some of them. However, the performance of these models would degrade significantly on low-resource data, even worse than conventional shallow models in some cases. In this work, we combat with the curse of data-inefficiency with the help of transfer learning for both language understanding and generation tasks. First, I will introduce MMM, a Multi-stage Multi-task learning framework for the Multi-choice Question Answering (MCQA) task, which brings in around 10% of performance improvement on 5 MCQA low-resource datasets. Second, an iterative back-translation (IBT) schema is proposed to boost the performance of machine translation models on zero-shot domains (with no labeled data) by adapting from the source domain with large-scale labeled data.

 
Biography:
Di Jin is a fifth year PhD student at MIT working with Prof. Peter Szolovits. He works on Natural Language Processing (NLP) and its applications into biomedical and clinical domains. Previous works focused on sequential sentence classification, transfer learning for low-resource data, adversarial attacking and defense, and text editing/rewriting.

 
Join Zoom Meeting:
https://cuhk.zoom.us/j/834299320
https://cuhk.zoom.com.cn/j/834299320(Mainland China)
Meeting ID: 834 299 320
Find your local number: https://cuhk.zoom.us/u/abeVNXWmN

 
Enquiries: Miss Caroline Tai at Tel. 3943 8440
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar-archive/

Speaker:
Prof. Patrick Lee Pak Ching
Associate Professor
Department of Computer Science and Engineering
The Chinese University of Hong Kong

 
Abstract:
Modern decentralized key-value stores often replicate and distribute data via consistent hashing for availability and scalability. Compared to replication, erasure coding is a promising redundancy approach that provides availability guarantees at much lower cost. However, when combined with consistent hashing, erasure coding incurs a lot of parity updates during scaling (i.e., adding or removing nodes) and cannot efficiently handle degraded reads caused by scaling. We propose a novel erasure coding model called FragEC, which incurs no parity updates during scaling. We further extend consistent hashing with multiple hash rings to enable erasure coding to seamlessly address degraded reads during scaling. We realize our design as an in-memory key-value store called ECHash, and conduct testbed experiments on different scaling workloads in both local and cloud environments. We show that ECHash achieves better scaling performance (in terms of scaling throughput and degraded read latency during scaling) over the baseline erasure coding implementation, while maintaining high basic I/O and node repair performance.

 
Speaker’s Bio:
Patrick Lee is now an Associate Professor at CUHK CSE. Please refer to http://www.cse.cuhk.edu.hk/~pclee.

 
Enquiries: Ms. Shirley Lau at tel. 3943 8439
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar-archive/

Speaker:
Prof. Hermann KOPETZ
Professor Emeritus
Technical University of Vienna

Abstract:
The human effort required to understand, design, and maintain a software system depends on the complexity of the artifact. After a short introduction into the different facets of complexity, this talk deals with the characteristics of multi-level models and the appearance of emergent phenomena.  The focus of the core section of the talk is a discussion of simplification principles in the design of Cyber-Physical Systems. The most widely used simplification principle, divide and conquer, partitions a large system horizontally, temporally, or vertically into nearly independent parts that are small enough in order that their behavior can be understood considering the limited capacity of the human cognitive appparatus. The most effective—and difficult—simplification principle is the new conceptualization of the emergent properties of interacting parts.

A more detailed discussion of the topic is contained in the upcoming book: Simplicity is Complex, Foundations of Cyber-Physical System Design that will be published by Springer Verlag in the summer of 2019.

Speaker’s Bio:
Hermann Kopetz received a PhD degree in Physics sub auspiciis praesidentis from the University in Vienna in 1968 and is since 2011 professor emeritus at the Technical University of Vienna. He is the chief architect of the time-triggered technology for dependable embedded Systems and a co-founder of the company TTTech. The time-triggered technology is deployed in leading aerospace, automotive and industrial applications. Kopetz is a Life Fellow of the IEEE and a full member of the Austrian Academy of Science. He received a Dr. honoris causa degree from the University Paul Sabatier in Toulouse in 2007.  Kopetz served as the chairman of the IEEE Computer Society Technical Committee on Dependable Computing and Fault Tolerance and in program committees of many scientific conferences. He is a founding member and a former chairman of IFIP WG 10.4. Kopetz has written a widely used textbook on Real-Time Systems (that has been translated to Chinese) and published more than 200 papers and 30 patents.

Enquiries: Ms. Shirley Lau at tel. 3943 8439
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar-archive/

Speaker:
Dr. Joshua Ho
Associate Professor
School of Biomedical Sciences
University of Hong Kong

 
Abstract:
Single cell RNA-seq and other high throughput technologies have revolutionised our ability to interrogate cellular heterogeneity, with broad applications in biology and medicine. Standard bioinformatics pipelines are designed to process individual data sets containing thousands of single cells. Nonetheless, data sets are increasing in size, and some biological questions can only be addressed by performing large-scale data integration. There is a need to develop scalable bioinformatics tools that can handle large data sets (e.g., with >1 million cells). Our laboratory has been developing scalable bioinformatics tools that make use of modern cloud computing technology, fast heuristic algorithms, and virtual reality visualisation to support scalable data processing, analysis, and exploration of large single cell data. In this talk, we will describe some of these tools and their applications.

 
Speaker’s Bio:
Dr Joshua Ho is an Associate Professor in the School of Biomedical Sciences at the University of Hong Kong (HKU). Dr Ho completed his BSc (Hon 1, Medal) and PhD in Bioinformatics from the University of Sydney, and undertook postdoctoral research at the Harvard Medical School. His research focuses on advanced bioinformatics technology, ranging from scalable single cell analytics, metagenomic data analysis, and digital healthcare technology (such as mobile health, wearable devices, and healthcare artificial intelligence). Dr Ho has over 80 publications, including first or senior-author papers in leading journals such as Nature, Genome Biology, Nucleic Acids Research and Science Signaling. His research excellence has been recognized by the 2015 NSW Ministerial Award for Rising Star in Cardiovascular Research, the 2015 Australian Epigenetics Alliance’s Illumina Early Career Research Award, and the 2016 Young Tall Poppy Science Award.

 
Enquiries: Ms. Shirley Lau at tel. 3943 8439
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar-archive/

Speaker:
Prof. Keith L. Clark
Emeritus Professor
Imperial College London

 
Abstract:
Teleo-Reactive (TR) robotic agent programs comprise sequences of guarded action rules clustered into named parameterised procedures. Their ancestry goes back to the first cognitive robot, Shakey. Like Shakey, a TR programmed robotic agent has a deductive Belief Store comprising constantly changing predicate logic percept facts, and fixed knowledge facts and rules for querying the percepts.  In this paper we introduce TR programming using a simple example expressed in the teleo-reactive programming language TeleoR, which is a syntactic extension of QuLog, a typed logic programming language used for the agent’s Belief Store. The example program illustrates key properties that a TeleoR program should have.  We give formal definitions of these key properties, and an informal operational semantics of the evaluation of a TeleoR procedure call.  We then formally express the key properties in LTL. Finally we show how their LTL formalisation can be used to prove key properties of TeleoR procedures using the example TeleoR program.

 
Speaker’s Bio:
Keith Clark has Bachelor degrees in both mathematics and philosophy and a PhD in Computational Logic. He is one of the founders of Logic Programming.  His early research was primarily in the theory and practice of LP. His paper: “Negation as Failure” (1978), giving a semantics to Prolog’s negation operator, has over 3000 citations.

In 1981, inspired by Hoare’s CSP, with a PhD student Steve Gregory, he introduced the concepts of committed choice non-determinism and stream communicating and-parallel sub-proofs into logic programming.   This restriction of the LP concept was then adopted by the Japanese Fifth Generation Project.  This had the goal of building multi-processor knowledge using computers. Unfortunately, the restrictions men it is not a natural tool for building KP applications, and the FGP project failed.  Since 1990 his research emphasis has been on the design, implementation and application of multi-threaded rule based programming languages, with a strong declarative component, for multi-agent and cognitive robotic applications.

He has had visiting positions at Stanford University, UC Santa Cruz, Syracuse University and Uppsala University amongst others. He is currently an Emeritus Professor at Imperial, and an Honorary Professor at University of Queensland and the University of New Soul Wales.  He has consulted for the Japanese Fifth Generation Project, Hewlett Packard, IBM,  Fujitsu and two start-ups. With colleague Frank McCabe, he founded the company Logic Programming Associates in 1980. This produced and marketed Prolog systems for micro-computers, offering training and consultancy on their use. The star product was MacProlog,  with primitives for exploiting the Mac GUI for AI applications.

 
Enquiries: Ms. Shirley Lau at tel. 3943 8439
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar-archive/

Speaker:
Dr. Jiang Long
Apple silicon division

 
Abstract:
In LEC system, we present a learning-based framework to solve the data-path equivalence checking problem in a high-level synthesis design flow, which is gaining popularity in modern day SoC design process where CPU cores are accompanied by dedicated accelerators for computation intensive applications. In such a context, the data-path logic is no longer a ‘pure’ data computation logic but rather an arbitrary sea-of-logic, where highly optimized computation intensive arithmetic components are surrounded by a web of custom control logic. In such a setting, the state-of-art SAT-sweeping framework at the Boolean level is no longer effective as the specification and implementation under comparison may not have any internal structural similarities. LEC employs an open architecture, iterative compositional proof strategies, and a learning framework to locate, isolate and reverse engineer the true bottlenecks in order to reason about their equivalence relation at a higher level. The effectiveness of LEC procedures is demonstrated by benchmarking results on a set of realistic industrial problems.

 
Speaker’s Bio:
Jiang graduated from Computer Science Department at Jilin University, Changchun, China in 1992. In 1996, Jiang entered the graduate program in Computer Science at Tsinghua University, Beijing, China. A year later, from 1997 to 1999, Jiang studied in Computer Science Department at University of Texas at Austin as a graduate student. It is during the years at UT-Austin, Jiang developed an interest and focused in the field of formal verification of digital systems ever since. Between 2000 and 2014, Jiang worked on EDA formal verification tool development at Synopsys Inc and later at Mentor Graphics Corporation. Since March 2014, Jiang worked at Apple silicon division on SoC design formal verification and currently focusing on verification methodology and tool development for Apple CPU design and verification. While working in industry, between 2008 and 2017, Jiang completed his PhD degree at EECS Department in University of California at Berkeley in the area of logic synthesis and verification. Jiang ‘s dissertation work is on reasoning about high-level constructs for hardware and software formal verification in the context of high-level synthesis design flow.

 
Enquiries: Ms. Shirley Lau at tel. 3943 8439
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar-archive/

Speaker:
Prof. Yanzhi Wang
Department of Electrical and Computer Engineering
Northeastern University

 
Abstract:
This presentation focuses on two recent contributions on model compression and acceleration of deep neural networks (DNNs). The first is a systematic, unified DNN model compression framework based on the powerful optimization tool ADMM (Alternating Direction Methods of Multipliers), which applies to non-structured and various types of structured weight pruning as well as weight quantization technique of DNNs. It achieves unprecedented model compression rates on representative DNNs, consistently outperforming competing methods. When weight pruning and quantization are combined, we achieve up to 6,635X weight storage reduction without accuracy loss, which is two orders of magnitude higher than prior methods. Our most recent results conducted a comprehensive comparison between non-structured and structured weight pruning with quantization in place, and suggest that non-structured weight pruning is not desirable at any hardware platform.

However, using mobile devices as an example, we show that existing model compression techniques, even assisted by ADMM, are still difficult to translate into notable acceleration or real-time execution of DNNs. Therefore, we need to go beyond the existing model compression schemes, and develop novel schemes that are desirable for both algorithm and hardware. Compilers will act as the bridge between algorithm and hardware, maximizing parallelism and hardware performance. We develop a combination of pattern pruning and connectivity pruning, which is desirable at all of theory, algorithm, compiler, and hardware levels. We achieve 18.9ms inference time of large-scale DNN VGG-16 on smartphone without accuracy loss, which is 55X faster than TensorFlow-Lite. We can potentially enable 100X faster and real-time execution of all DNNs using the proposed framework.

 
Speaker’s Bio:
Prof. Yanzhi Wang is currently an assistant professor in the Department of Electrical and Computer Engineering at Northeastern University. He has received his Ph.D. Degree in Computer Engineering from University of Southern California (USC) in 2014, and his B.S. Degree with Distinction in Electronic Engineering from Tsinghua University in 2009.

Prof. Wang’s current research interests mainly focus on DNN model compression and energy-efficient implementation (on various platforms). His research maintains the highest model compression rates on representative DNNs since 09/2018. His work on AQFP superconducting based DNN acceleration is by far the highest energy efficiency among all hardware devices. His work has been published broadly in top conference and journal venues (e.g., ASPLOS, ISCA, MICRO, HPCA, ISSCC, AAAI, ICML, CVPR, ICLR, IJCAI, ECCV, ICDM, ACM MM, DAC, ICCAD, FPGA, LCTES, CCS, VLDB, ICDCS, TComputer, TCAD, JSAC, TNNLS, Nature SP, etc.), and has been cited around 5,000 times. He has received four Best Paper Awards, has another eight Best Paper Nominations and three Popular Paper Awards.

 
Enquiries: Ms. Shirley Lau at tel. 3943 8439
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar-archive/

Speaker:
Prof. Artur Andrzejak
University of Heidelberg
Germany

 
Abstract:
Data processing and analysis becomes relevant for a growing number of domains and applications, ranging from natural science to industrial applications. Given the variety of scenarios and the need for flexibility, each project typically require custom programming. This task might pose a challenge for the domain specialists (typically non-developers), and frequently becomes a major cost and time factor in crafting a solution. This problem even aggravates if performance or scalability are important, due to increased complexity of developing parallel/distributed software.

This talk focuses on selected solutions of these challenges. In particular, we will discuss a tool NLDSL [1] for accelerated implementation of Domain Specific Languages (DSLs) for libraries following the “fluent interface” programming model. We showcase how this solution facilitates script development in context of popular data science frameworks/libraries like (Python) Pandas, scikit-learn, Apache Spark, or Matplotlib. The key elements are “no overhead” integration of DSL and Python code, DLS-level code recommendations, and support for adding ad-hoc DSL elements tailored to even small application domains.

We will also discuss solutions utilizing machine learning. One of them are code fragment recommenders. Here frequently used code fragments (snippets) are extracted from Stackoveflow/GitHub, generified, and stored in a database. During development they are recommended to users based on textual queries, selection of relevant data, user interaction history, and other inputs.

Another work attempts to combine the approach for Python code completion via neural attention and pointer networks by Jian Li et al. [2] with probabilistic models for code [3]. Our study shows some promising improvement of accuracy.

If time permits, we will also take a quick look at alternative approaches for accelerated programming in context of data analysis: natural language interfaces for code development (e.g. bots), and the emerging technologies for program synthesis.

[1] Artur Andrzejak, Kevin Kiefer, Diego Costa, Oliver Wenz, Agile Construction of Data Science DSLs (Tool Demo), ACM SIGPLAN Int. Conf. on Generative Programming: Concepts & Experiences (GPCE), 21-22 October 2019, Athens, Greece.
[2] Jian Li, Yue Wang, Michael R. Lyu, and Irwin King, Code completion with neural attention and pointer networks. In Proc. 27th International Joint Conference on Artificial Intelligence (IJCAI’18), 2018, AAAI Press.
[3] Pavol Bielik, Veselin Raychev, and Martin Vechev. PHOG: Probabilistic model for code. In Prof. 33rd International Conference on Machine Learning, 20–22 June 2016, New York, USA.

 
Speaker’s Bio:
Artur Andrzejak has received a PhD degree in computer science from ETH Zurich in 2000 and a habilitation degree from FU Berlin in 2009. He was a postdoctoral researcher at the HP Labs Palo Alto from 2001 to 2002 and a researcher at ZIB Berlin from 2003 to 2010. He was leading the CoreGRID Institute on System Architecture (2004 to 2006) and acted as a Deputy Head of Data Mining Department at I2R Singapore in 2010. Since 2010 he is a W3-professor at University of Heidelberg and leads there the Parallel and Distributed Systems group. His research interests include scalable data analysis, reliability of complex software systems, and cloud computing. To find out more about his research group, visit http://pvs.ifi.uni-heidelberg.de/.

 
Enquiries: Ms. Shirley Lau at tel. 3943 8439
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar-archive/

Speaker:
Prof. Michael R. Lyu
Professor and Chairman
Computer Science & Engineering Department
The Chinese University of Hong Kong

 
Abstract:
Publish or Perish.  This is the pressure of most academic researchers.  Even if your advisor(s) do not ask you to publish a certain number of papers as the graduation requirement, performing high quality research is still essential. In this talk I will share my experience in the question all graduate students will ask, “How to do high quality research and write acceptable papers?”

 
Speaker’s Bio:
Michael Rung-Tsong Lyu is a Professor and Chairman of Computer Science and Engineering Department at The Chinese University of Hong Kong. He worked at the Jet Propulsion Laboratory, the University of Iowa, Bellcore, and Bell Laboratories. His research interests include software reliability engineering, distributed systems, fault-tolerant computing, service computing, multimedia information retrieval, and machine learning. He has published 500 refereed journal and conference papers in these areas, which recorded 30000 Google Scholar citations and h-index of 85. He served as an Associate Editor of IEEE Transactions on Reliability, IEEE Transactions on Knowledge and Data Engineering (TKDE), Journal of Information Science and Engineering, and IEEE Transactions on Services Computing. He is currently on the editorial boards of ACM Transactions on Software Engineering and Methodology (TOSEM), IEEE Access, and Software Testing, Verification and Reliability Journal (STVR). He was elected to IEEE Fellow (2004), AAAS Fellow (2007), Croucher Senior Research Fellow (2008), IEEE Reliability Society Engineer of the Year (2010), ACM Fellow (2015), and received the Overseas Outstanding Contribution Award from China Computer Federation in 2018.  Prof. Lyu received his B.Sc. from National Taiwan University, his M.Sc. from University of California, Santa Barbara, and his Ph.D. in Computer Science from University of California, Los Angeles.

 
Enquiries: Ms. Shirley Lau at tel. 3943 8439
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar-archive/

Speaker:
Prof. Martin Charles Golumbic
University of Haifa

 
Abstract:
Graph sandwich problems are a prototypical example of checking consistency when faced with only partial data. A sandwich problem for a graph with respect to a graph property $\Pi$ is a partially specified graph, i.e., only some of the edges and non-edges are given, and the question to be answered is, can this graph be completed to a graph which has the property $\Pi$? The graph sandwich problem was investigated for a large number of families of graphs in a 1995 paper by Golumbic, Kaplan and Shamir, and over 200 subsequent papers by many researchers have been published since.

In some cases, the problem is NP-complete such as for interval graphs, comparability graphs, chordal graphs and others. In other cases, the sandwich problem can be solved in polynomial time such as for threshold graphs, cographs, and split graphs. There are also interesting special cases of the sandwich problem, most notably the probe graph problem where the unspecified edges are confined to be within a subset of the vertices. Similar sandwich problems can also be defined for hypergraphs, matrices, posets and Boolean functions, namely, completing partially specified structures such that the result satisfies a desirable property. In this talk, we will present a survey of results that we and others have obtained in this area during the past decade.

 
Speaker’s Bio:
Martin Charles Golumbic is Emeritus Professor of Computer Science and Founder of the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science at the University of Haifa. He is the founding Editor-in-Chief of the journal “Annals of Mathematics and Artificial Intelligence” and is or has been a member of the editorial boards of several other journals including “Discrete Applied Mathematics”, “Constraints” and “AI Communications”. His current area of research is in combinatorial mathematics interacting with real world problems in computer science and artificial intelligence.

Professor Golumbic received his Ph.D. in mathematics from Columbia University in 1975 under the direction of Samuel Eilenberg. He has held positions at the Courant Institute of Mathematical Sciences of New York University, Bell Telephone Laboratories, the IBM Israel Scientific Center and Bar-Ilan University. He has also had visiting appointments at the Université de Paris, the Weizmann Institute of Science, Ecole Polytechnique Fédérale de Lausanne, Universidade Federal do Rio de Janeiro, Rutgers University, Columbia University, Hebrew University, IIT Kharagpur and Tsinghua University.

He is the author of the book “Algorithmic Graph Theory and Perfect Graphs” and coauthor of the book “Tolerance Graphs”. He has written many research articles in the areas of combinatorial mathematics, algorithmic analysis, expert systems, artificial intelligence, and programming languages, and has been a guest editor of special issues of several journals. He is the editor of the books “Advances in Artificial Intelligence, Natural Language and Knowledge-based Systems”, and “Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications”. His most recent book is “Fighting Terror Online: The Convergence of Security, Technology, and the Law”, published by Springer-Verlag.

Prof. Golumbic and was elected as Foundation Fellow of the Institute of Combinatorics and its Applications in 1995, and has been a Fellow of the European Artificial Intelligence society ECCAI since 2005. He is a member of the Academia Europaea, honoris causa — elected 2013. Martin Golumbic has been the chairman of over fifty national and international symposia. He a member of the Phi Beta Kappa, Pi Mu Epsilon, Phi Kappa Phi, Phi Eta Sigma honor societies and is married and the father of four bilingual, married daughters and has seven granddaughters and five grandsons.

 
Enquiries: Ms. Shirley Lau at tel. 3943 8439
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar-archive/