Biography

Anand Raghunathan, the Silicon Valley Professor of Electrical and Computer Engineering, has been chosen to receive Purdue’s 2023 Arden L. Bement Jr. Award. The award is given annually to a university researcher who has made highly significant and impactful contributions to pure and applied sciences and engineering. Raghunathan is being recognized for his pioneering work in making artificial intelligence (AI) systems more energy-efficient through specialized hardware architectures for AI workloads and the design paradigm of approximate computing.

A fellow of the Institute of Electrical and Electronics Engineers and the Association for Computing Machinery, Raghunathan has been a Purdue faculty member since 2008. He is a founding codirector of the Purdue-led Center for a Secured Microelectronics Ecosystem and codirector of the Center for the Co-design of Cognitive Systems funded by the Semiconductor Research Corp. and the U.S. Defense Advanced Research Projects Agency.

“Anand was one of the very first researchers to realize that machine learning and data analytics would drive the future of computing platforms and their underlying hardware fabrics. His group created some of the first hardware accelerators for AI workloads, in the process recognizing the need for new design paradigms to create such hardware,” said Kaushik Roy, the Edward G. Tiedemann Jr. Distinguished Professor of Electrical and Computer Engineering, in nominating Raghunathan. “This led him to his pioneering work in approximate computing, which has deeply influenced subsequent efforts in academia and industry and has been recognized with best paper and test-of-time awards.”

“I am deeply honored to be chosen to receive this award,” Raghunathan said. “I am indebted to all my mentors, collaborators and students over the years, and to Purdue for providing an amazing environment in which to pursue my research.”

Looking ahead to future challenges, Raghunathan has clearly defined his priorities: “Artificial Intelligence has fundamentally altered the trajectory of demand for computing. Our ability to address the AI compute efficiency challenge will shape the future of AI and many other fields. I hope to tackle this challenge through my work.”

“Prof. Raghunathan’s pioneering research in utilizing approximate computing techniques for improving the efficiency of AI hardware — specifically, trained quantization of deep neural networks — has been foundational to enabling transformative advances in AI systems in recent years across the industry,” said Vivek De, Intel fellow and director of circuit technology research.

Among many accolades, Raghunathan was cited as one of the world’s top 35 innovators under the age of 35 by MIT Technology Review magazine. He has received nine best paper awards, a ten-year retrospective most influential paper award and a best design contest award at premier conferences in his field. Before joining Purdue, he received a Patent of the Year Award and two Technology Commercialization Awards from NEC Corp. for his work that shaped multiple generations of semiconductor products. At Purdue, he has received the College of Engineering Faculty Excellence Award for Research, the Qualcomm Faculty Award and the IBM Faculty Award.

Abstract

AI’s Energy Challenge and four A’s to Address it
Artificial Intelligence is transforming the landscape of computing and in turn several facets of our lives. Creating or using an AI model has an important, and often invisible, by-product—energy consumption in the underlying computing system that the model runs on. The meteoric improvements in AI systems that we have witnessed over the past decade have been accompanied by equally rapid increases in their appetite for energy. Is this trend sustainable? How can the computing industry ensure that progress in AI is not gated by energy costs? We will explore the energy footprint of today’s AI systems and discuss four A’s—Awareness, Algorithms, Application-specific hardware, and Approximate computing—that can pave the way towards a future with energy-efficient AI.

Dr. Manfra discusses experiments conducted at Purdue that reveal how anyons, particles with fractional charge and fractional statistics, may be observed in simple electrical conduction measurements.

Biography

Michael Manfra is the Bill and Dee O’Brien Distinguished Professor of Physics and Astronomy, Professor of Material Science Engineering, and Professor of Electrical and Computer Engineering at Purdue University. Mike received his A.B. degree from Harvard in 1992 followed by his M.S. in 1994 and PhD from Boston University in 1999. Mike spent 2 years as a Postdoctoral Member of the Technical Staff at Bell Laboratories, Lucent Technologies and in 2001 became a member of the Technical Staff of Bell Laboratories where he carried out research in low dimensional electron systems. In 2009 Manfra moved to Purdue as the William F. and Patty J. Miller Associate Professor of Physics and Astronomy, Materials Engineering, and Electrical and Computer Engineering. Mike was a Keck Foundation awardee in 2013 and was promoted to Full Professor in the same year. He was named a University Faculty Scholar in 2013. He was elected a Fellow of the American Physical Society in 2015 and in 2016 became the Director of Microsoft Quantum Lab Purdue, one of a small handful of Microsoft Quantum Laboratories around the globe. Since 2018 he is a member of the Birck Faculty Leadership Council. In 2020 Mike became a Distinguished Professor of Physics and Astronomy.

Abstract

Fractionalization of Charge and Statistics in Two Dimensions
A basic tenet of quantum mechanics is that all elementary particles are either bosons or fermions. Ensembles of bosons and fermions act differently due to differences in their statistical properties. For example, much of the electronic structure of ordinary solids may be explained by symmetry and noting electrons are fermions and obey the Pauli exclusion principle – fermions cannot exist in the same quantum state simultaneously. On the other hand, integer spin atoms and photons are bosons and are not constrained by the Pauli principle. Bose-Einstein condensation and superfluidity are some of the most spectacular properties of bosons. Starting in the early 1980’s it was theoretically conjectured that excitations that are neither bosons nor fermions may exist under special conditions in two dimensional systems. These unusual excitations were dubbed “anyons”. Anyons may have fractional charge and fractional statistics, however directly probing these properties presents experimental challenges. My talk will focus on experiments that demonstrate fractional statistics have observable consequences.

Biography

Kaushik Roy is the Edward G. Tiedemann, Jr., Distinguished Professor of Electrical and Computer Engineering at Purdue University and Director of the Center for Brain-Inspired Computing (C-BRIC). He received his PhD from University of Illinois at Urbana-Champaign in 1990 and joined the Semiconductor Process and Design Center of Texas Instruments, Dallas, where he worked for three years on FPGA architecture development and low-power circuit design. His current research focuses on algorithms, circuits and architecture for energy-efficient cognitive computing, computing models and neuromorphic devices. Roy has supervised more than 85 PhD dissertations, and his students are well-placed in universities and industry. He is the co-author of “Low Power CMOS VLSI Design,” both the first and second editions, published by John Wiley & McGraw Hill.

Roy has received a National Science Foundation Career Development Award, IBM Faculty Partnership Award, ATT/Lucent Foundation Award, Semiconductor Research Corporation Technical Excellence Award, SRC Inventors Award, Purdue College of Engineering Research Excellence Award, Humboldt Research Award, IEEE Circuits and Systems Society Technical Achievement Award (Charles Desoer Award), Distinguished Alumnus Award from the Indian Institute of Technology, and the Semiconductor Research Corporation Aristotle Award in 2015. He also has served as a Department of Defense Vannevar Bush Faculty Fellow; Global Foundries Visiting Chair at National University of Singapore and Fulbright-Nehru Distinguished Chair.

Abstract

Reengineering Computing with Neuro-Inspired Learning
Advances in machine learning have led to computers matching or surpassing human performance in several cognitive tasks including vision, speech and natural language processing. However, implementation of such neural algorithms in conventional von-Neumann architectures are orders of magnitude more inefficient in power than the biological brain. Hence, we need fundamentally new approaches to sustain the exponential growth in performance beyond the end of the CMOS technology roadmap. Exploring the new paradigm of computing necessitates a multidisciplinary approach: exploration of robust learning algorithms inspired from neuroscientific principles, development of network and hardware architectures best suited for such algorithms and the creation of nanoscale devices that can closely mimic the neuronal and synaptic operations of the brain leading to a better match between the hardware substrate and the model of computation. In this talk, Roy will focus on his recent works on neuromorphic computing and the design of underlying hardware that can lead to quantum improvements in energy efficiency with good accuracy.

Research Accomplishments

Roy’s research is founded on the key insight that today’s computing fabrics – based on the Silicon CMOS transistors and von Neumann computer architecture – are ill-matched to the building blocks (neurons and synapses) as well as the computing architecture of the brain. This mismatch is in large part responsible for the orders of magnitude energy gap observed between artificial and natural intelligence; machines such as Google’s AlphaGo and IBM’s Watson that have surpassed human competitors consume hundreds of thousands of watts while the human brain consumes only around 20 watts.

His research has pioneered a holistic algorithms-to-devices approach to bridging the efficiency gap between current AI systems and the brain by proposing devices that directly emulate the basic neuronal and synaptic operations, by designing new circuits and architectures that embody the key information processing principles of the brain and by creating algorithms that bridge these hardware fabrics to AI/ML applications.

• Neuromimetic devices and circuits: Roy’s group realized that the intrinsic physics of some of the emerging devices, including spintronics, could naturally emulate neurons and synapses of different bio-fidelity, leading to highly compact and energy-efficient hardware implementations, well beyond the capabilities of standard CMOS circuits. This is due to two factors – the inherent match between the characteristics of these devices and the functionality of a neuron/synapse/biological functions (leading to a drastic decrease in the number of devices required) and the possibility of ultra-low voltage operation.
• Neuro-mimetic hardware architectures: Even though the GPUs were instrumental in the rapid development of AI algorithms, their limitations in training and inference are apparent from the orders of magnitude energy efficiency gap that exists between the computing architecture of the brain and the von Neumann machines. This is mainly due to the memory bottleneck – the computation and storage are separate, leading energy-consuming traffic to fetch data from memory, computing in the processing unit and storing the results back to memory. To address such bottlenecks, and taking cues from the brain, Roy and his students developed new memory circuits that can effectively do processing of data in the memory itself.
• Learning and inference algorithms: Roy’s group has been instrumental in pioneering a new generation of bio-plausible spiking neural network (SNN) architectures and training algorithms to achieve state-of-the-art accuracy with superior energy efficiency compared to today’s artificial neural networks. His group developed new ways of training deep spiking networks with different types of spike-based input coding. They were the first to demonstrate deep SNNs (VGG-16, ResNet-34) capable of achieving state-of-the-art accuracy on industry strength datasets: CIFAR10 and ImageNet.

Biography

Evgenii Narimanov is a professor of electrical and computer engineering in the College of Engineering. He received his master’s degree in applied mathematics and physics and PhD in semiconductor physics from the Moscow Institute of Physics and Technology.

After working at Yale University, Bell Labs/Lucent Technologies, and Princeton University, Narimanov joined Purdue University in 2007 as an associate professor. He became full professor in 2013.

His current research includes nanophotonics, physics of metamaterials, and information theory for optical imaging. Narimanov’s work in optics and optoelectronics is recognized nationally and internationally. He has been credited with a series of research breakthroughs — from the development of the high-power microlasers with wave-chaotic dynamics, to the derivation of the fundamental information-theoretical limit on the communication rates in nonlinear fiber-optical networks. His pioneering work in hyperbolic metamaterials and discovery of the hyperlens has led to an optical device capable of resolution beyond the diffraction limit.

Narimanov has authored and co-authored four book chapters, more than 100 peer-reviewed articles, and has made more than 100 conference presentations, including many invited and keynote talks. He has been awarded six U.S. patents.

He has been named Purdue University Faculty Scholar and is the recipient of the National Science Foundation Career Award. He is a fellow of the Institute of Electrical and Electronics Engineers and the Optical Society of America.

Abstract

Optical Hyperspace: Light in Hyperbolic Metamaterials
Hyperbolic metamaterials are strongly anisotropic composite media that behave as either metals or dielectrics in different directions. They can be fabricated in many different ways, such as metallic layers that are separated from each other by thin dielectric spacers, or using arrays of parallel metallic nanowires in a dielectric material.

Unique optical properties of hyperbolic metamaterials — from negative refraction to diffraction-less propagation and subwavelength focusing to accelerated light emission to enhanced radiative heat transfer — are transforming the ways we think about optical imaging, light-wave communications, and electromagnetic energy harvesting.

Research Accomplishments

Narimanov is a pioneer in the research field of metamaterials that recently emerged on the crossroads of photonics and nanotechnology. He is known for his work on hyperbolic metamaterials, which are anisotropic composites with unique electromagnetic properties — an area that he introduced and developed into an exciting and groundbreaking field. Over the last decade, the studies of hyperbolic metamaterials grew to the point of forming an important and highly impactful field of optics and photonics, with about 2,000 research papers published per year in the subject.

Among many research accomplishments in science and engineering, Narimanov and his collaborators have:

• Pioneered the use of an information theory approach in the analysis of optical communications systems in nonlinear regime.
• Initiated the study of nanolasers with wave-chaotic dynamics, and demonstrated the role of optical Anderson localization in the performance of light-emitting devices.
• Discovered the singularity in the photonic density of states in hyperbolic metamaterials. This singularity has major impact on light absorption, emission, and reflection by structures made of hyperbolic metamaterials, and has far-reaching implications for the fundamental physics of optical media and many potential applications.
• Introduced the hyperlens, a high-resolution optical imaging device based on hyperbolic metamaterials that is considered one of the most exciting and innovative applications of metamaterials.
• Pioneered the concept of photonic hypercrystals that combine the properties of hyperbolic materials and photonic crystals and offer a dramatic improvement in the performance of ultra-fast, light-emitting diodes for optical communications and photonic interconnects.

Distinguished Lecture Video

Biography

Peide Ye is the Richard J. and Mary Jo Schwartz Professor of Electrical and Computer Engineering in the College of Engineering. He received his Bachelor of Science in electrical engineering in 1988 from Fudan University, Shanghai, China. Ye earned his PhD in condensed matter physics in 1996 from Max Planck Institute for Solid State Research in Stuttgart, Germany.

After working for NTT Basic Research Laboratories, the National High Magnetic Field Laboratory and Princeton University, and Bell Labs/Lucent Technologies/ Agere Systems, Ye joined Purdue in 2005 as an associate professor. He became a full professor in 2010 and a named professor in 2016.

His current research includes atomic semiconductor and physics devices, nanostructures and nanofabrications among other areas. Ye’s work in semiconductor technologies is recognized nationally and internationally, and he has been credited with a series of research breakthroughs. Each one was significant enough to be deemed “field-defining.”

Ye has authored and co-authored eight book chapters, more than 200 peer-reviewed articles and made 350 conference presentations, including many invited, keynote and plenary talks. He has been awarded five U.S. patents.

Ye has been the recipient of the Volkswagen Fellowship, the Max Planck Society Fellowship, the NTT Fellowship, the IBM Faculty Award, the Purdue College of Engineering Faculty Award of Excellence in Research and the Sigma Xi Research Award. He is a fellow of the Institute of Electrical and Electronics Engineers and the American Physical Society.

Abstract

Moore’s Law Extension and Beyond
Moore’s Law became the “golden rule” for the microelectronics industry and a springboard for innovation. Gordon Moore paved the path for Intel and others to make faster, smaller and more affordable transistors for our modern tools and toys.

In his talk, Ye will review his research efforts at Purdue on materials, structures and device architecture to support the microelectronic industry and extend Moore’s Law. The goal of the research is that it will lead to smarter, ubiquitous computing technology and keep us healthier, safer and more productive.

Research Accomplishments

Ye has made fundamental contributions to novel electronic materials and devices in recent years. He has an ability to enter a field, see where the roadblocks are, devise creative solutions and produce results. Among many research accomplishments in applied science and engineering, Ye and his collaborators have:

• Pioneered atomic layer deposited high-k dielectrics on III-V compound semiconductors and achieved record device performance in III-V metaloxide- semiconductor field-effect transistors (MOSFETs).
• Developed a new contact engineering process on n-type Ge material to achieve record device performance on Ge N-type MOSFETs and demonstrated the first Ge complementary metal-oxide-semiconductor (CMOS) devices and circuitry.
• Discovered a new doping technique on 2D material channels and demonstrated record device performance on MoS2 and WS2.
• Pioneered phosphorene and black phosphorus 2D research and systematically explored their anisotropic electrical, optical, thermal and mechanical properties.

Biography

Mikhail Atallah is a Distinguished Professor of Computer Science at Purdue University. He also is affiliated with the Center for Education and Research in Information Assurance and Security (CERIAS) and has a courtesy appointment in the School of Electrical and Computer Engineering.

He earned his Bachelor of Engineering degree in electrical engineering from American University in Beirut in 1975. He earned his Master’s degree and PhD in electrical engineering and computer science from The Johns Hopkins University in 1980 and 1982, respectively. After receiving his doctorate, he came to Purdue as an assistant professor of computer science. He was named associate professor in 1986, professor in 1989 and distinguished professor in 2004.

He has published over 255 archived journal research papers and coauthored 12 books and book chapters. Atallah has been awarded eight patents. In 2001, he co-founded Arxan Technologies Inc. to commercialize a security technology he developed with doctoral student Hoi Chang. Arxan became a successful, award-winning company, and it was acquired in 2013 by TA Associates, a private equity firm. The company’s technology is deployed in over 500 million devices.

Atallah has received several awards for his research and teaching, including the 2015 ACM Conference on Computer and Communications Security Test-of-Time Award, the 2013 Purdue Outstanding Commercialization Award and the Outstanding Teacher Award in the College of Science. He also is in Purdue’s Book of Great Teachers and is a member of the Purdue Teaching Academy. Atallah is a fellow of both the Association for Computing Machinery and the Institute of Electrical and Electronics Engineers. He is a recipient of the Purdue Sigma Xi Faculty Research Award.

Abstract

Opportunities and Perils of the Cyber Revolution
The ongoing cyber revolution has brought many benefits, and it holds the promise of many more in the future if some critical challenges can be overcome. One of these challenges is defending against the enormous cyber threats, whose potential for future devastation far exceeds the damage done by the attacks that have already taken place. Another challenge is enhancing our ability to carry out complex computational tasks on massive data sets. Whereas the ability to carry out computations generally contributes to achieving benefits from the cyber revolution, and the impossibility of carrying out computations generally detracts from achieving those benefits, computational impossibility can be beneficial to cyber defense when it is used to build defenses whose proper functioning depends on that impossibility. The security of many widely deployed defensive mechanisms relies on the attackers’ inability to solve some computationally hard problems, so that a computational breakthrough for such problems can have adverse security consequences. In this talk, Professor Atallah will discuss these issues and present his information-security research toward mitigating cyber threats and his algorithmic work toward efficiently carrying out computations on massive data sets.

Research Accomplishments

Among his many research accomplishments, Professor Atallah and his collaborators have:

• Settled a longstanding problem in data structuring for efficiently processing an important class of range queries.
• Designed a technique for key management in access hierarchies.
• Developed a divide-and-conquer technique to parallelize sequential algorithms that resulted in the first optimal parallel algorithms for a large number of geometric and combinatorial problems.
• Developed and commercialized a software protection technology that is used in millions of computing devices.
• Settled a longstanding problem in data filtering. Atallah is working on protocols to allow online collaborators to make computations that depend on confidential individual inputs without revealing any participant’s input to other participants.

Biography

Arvind Varma joined Purdue University in January 2004 as the R. Games Slayter Distinguished Professor and Head, School of Chemical Engineering – he was named Jay and Cynthia Ihlenfeld Head in 2012 and continued in this position until July 31, 2016. Prior to joining Purdue, he was the Arthur J. Schmitt Professor of Chemical Engineering and Director of the Center for Molecularly Engineered Materials at the University of Notre Dame. A native of India, he received his Ph.D. degree in Chemical Engineering from the University of Minnesota (1972). He remained at Minnesota for one year as an assistant professor, and was a senior research engineer with Union Carbide Corporation for two years before joining the Notre Dame faculty in 1975. He achieved the rank of full Professor in 1980, received the Schmitt Chair position in 1988, and was named founding Director of the Center for Molecularly Engineered Materials in the year 2000.

Varma’s research interests are in chemical and catalytic reaction engineering, new energy sources and synthesis of advanced materials. He has published over 295 archival journal research papers in these areas, co-authored three books and co-edited two books. As mentor, Varma has directed 46 completed Ph.D. dissertations, and the research of 30 post-doctoral research associates. He is the founding Editor (1996-present) of the Cambridge Series in Chemical Engineering, a series of textbooks and monographs published by the Cambridge University Press.

Varma has held Visiting Professorships at a number of institutions, including Caltech, Princeton, University of Wisconsin, University of Minnesota, Univ of Cagliari – Italy, IIT-Kanpur and UICT-Mumbai.  He has received various recognitions for his research and teaching, including AIChE’s R.H. Wilhelm (1993) and W.K. Lewis (2013) awards, and the Chemical Engineering Lectureship Award of the American Society for Engineering Education (2000).  He is a Fellow of AIChE and of the American Association for the Advancement of Science.

Abstract

Selected Topics Related to Energy and Chemicals
In the presentation, some selected research programs to produce energy carriers and valuable chemicals from new or renewable sources, currently being conducted or recently completed in my laboratory, will be discussed. These include (i) hydrogen generation for PEM fuel cell vehicle applications, (ii) catalytic upgrading of bio-oils, (iii) utilization of glycerol, a biodiesel waste product, for production of valuable chemicals, and (iv) oxidative coupling of methane.  The research relies on development of new catalytic materials and/or processes and demonstrates successful applications of the principles of chemical and catalytic reaction engineering to solve problems of contemporary interest facing society.

Research Accomplishments

Through his creative experimental and theoretical research, Arvind Varma has made pioneering contributions to the chemical reaction engineering (CRE) discipline.  Within this field, his publications focus on the understanding, analysis and design of chemical and catalytic reacting systems, synthesis of advanced materials, and new energy sources.

Varma’s early work dealt with analysis of reactor steady state multiplicity and stability, diffusion-reaction in catalyst pellets, yield optimization in complex reaction networks, automotive exhaust catalysis, multiphase reactors, and development of reactor models validated by experiments.  Then, in a series of landmark publications, Varma and his coworkers produced the first systematic and definitive works on two subjects of central importance in CRE: (1) optimal distribution of catalyst in pellets, and (2) parametric sensitivity and runaway behavior.  His works on these topics are summarized in two scholarly monographs:

• Catalyst Design: Optimal Distribution of Catalyst in Pellets, Reactors and Membranes, 227 pages, Cambridge University Press (2001).
• Parametric Sensitivity in Chemical Systems, 342 pages, Cambridge University Press (1999).

Varma is well-known world-wide for his contributions in combustion synthesis of advanced materials.  He developed principles for combustion synthesis and introduced several novel techniques in the literature (e.g. microscopic high-speed videorecording, computer-assisted electrothermography, quenching, and particle-foil experiments), which are used to control the microstructure, and hence the properties, of advanced materials such as intermetallics, ceramics and their composites.  

Varma is also a leader in inorganic membranes and membrane reactors.  He developed a novel method  (electroless plating with osmosis) for synthesis of palladium-based composite membranes, which exhibit higher hydrogen permeability and thermal stability than achieved by conventional techniques.  These membranes are used for hydrogen separation from gas mixtures and for obtaining supra-equilibrium yield in reactions involving hydrogen as a product.  He also demonstrated elegantly, both by careful experiments and theory, that conversion and yield of commercially important epoxidation and oxidative dehydrogenation reactions can be improved significantly by use of inorganic membrane distributed-feed reactors. 

In recent years, Varma has focused his research on energy-related topics, among which the first involves hydrogen generation.  He invented an award winning new method to generate hydrogen for portable fuel cells.  He has also developed novel methods to generate hydrogen on-board vehicles near PEM fuel cell operating temperatures, which provide the highest hydrogen yield (12-15 wt%) reported in the literature.  His publications deal not only with developing new methods and optimizing the operating conditions for maximum hydrogen yield, but also with the reaction mechanisms to provide an understanding of the reasons underlying the high hydrogen yield. 

Other recent energy-related topics include underground coal gasification; chemical looping combustion for power plants; utilization of glycerol, a waste product of biodiesel production; lipase catalyzed biodiesel production; oxidative coupling of methane; and catalytic deoxygenation of model compounds in pyrolysis bio-oils.

In addition to his focus on energy research, Varma has also published recently on experimental and modeling studies of trickle-bed catalytic reactors which are commonly employed in the petroleum, chemical and pharmaceutical industries.

Biography

Wojciech Szpankowski is the Saul Rosen Professor of Computer Science at Purdue University. Born in Poland, he received his master’s and doctorate degrees in Electrical Engineering and Computer Science from the Technical University of Gdansk.

He has held several Visiting Professor/Scholar positions, including Stanford, Hewlett-Packard Labs, INRIA, Ecole Polytechnique (France), the Newton Institute, (Cambridge, United Kingdom), Technology University of Gdansk (Poland), and ETH (Zurich). He is a Fellow of IEEE, the Erskine Fellow and 2010 recipient of the Humboldt Research Award. His research interests cover analysis of algorithms, information theory, bioinformatics, analytic combinatorics and stability problems of distributed systems.

Szpankowski also has written two books. “Average Case Analysis of Algorithms on Sequences” is about generating function methodology as applied in the analysis of algorithms. His second book, co-authored with Philippe Jacquet, “Analytic Pattern Matching: From DNA to Twitter,” was published by Cambridge University Press in 2015.

Szpankowski has been a guest editor and an editor of several technical journals, including ACM Transaction on Algorithms, Algorithmica, IEEE Transactions on Information Theory, and Combinatorics, Probability and Computing.

In 2008 he launched the interdisciplinary Institute for Science of Information, whose mission is to extend classical information theory to modern settings, including knowledge discovery and information extraction from massive datasets. He is director of the Purdue Center for Science of Information (CSoI), a National Science Foundation-funded Science and Technology Center in Discovery Park.

Abstract

Our current understanding of information dates back to Claude Shannon’s seminal work in 1948, resulting in a general mathematical theory of reliable communication. This theory, broadly referred to as information theory, provided the formal basis for modern digital communication and storage systems.

Analytic information theory addresses problems of information theory using tools of analytic combinatorics. Following Jacques Hadamard’s precept (“The shortest path between two truths in the real domain passes through the imaginary one.”), our work tackles these problems using methods of complex analysis, such as generating functions, Mellin transform, Fourier series, saddle-point method, analytic poissonization and depoissonization, and singularity analysis.

In this talk, after reviewing two main results of Shannon’s work concerning compression and reliable communication, we show how a small modification to the underlying model — to bring it closer to modern-day applications — may render these problems almost intractable. In particular, we present our recent solution to the so-called “noisy constrained capacity” problem, left open since Shannon. This problem finds applications ranging from state-of-the-art storage technologies to computational biology.

In the second part of the talk, we present models and methods for quantifying information embodied in structures. In particular, we present a fundamental lower bound for structural compression and describe a novel algorithm that achieves this lower bound. We demonstrate the significant benefits and broad application scope of our method. We conclude with some challenges for future research.

Research Accomplishments

Professor Szpankowski is known for his foundational work in analytic combinatorics, analysis of algorithms and analytic information theory.

He has made seminal contributions to the emergence of these areas as an organized field of research, evolving from a collection of results on individual problems to a broad and deep discipline with general applicability.

The discipline integrates classical methods of analysis, information, combinatorics and discrete probability to address challenges in data and algorithm analysis. Szpankowski’s scholarship and leadership in this field brought the National Science Foundation’s first Science and Technology Center to Indiana, the Purdue Center for Science of Information (CSoI).

The center, located in Discovery Park, brings the best minds together from across the nation to further the research generated from Shannon’s theory. As director, Szpankowski leads an interdisciplinary team to extend the classical information theory to modern settings through knowledge discovery and information extraction from massive datasets.

Szpankowski has made contributions in three technical areas: stability of computer networks, analysis of algorithms, and information theory (specifically, in data compression).

Stability is a fundamental issue in the design of any distributed system. Typically in an unstable network, the expected number of items (packets, messages, etc.) waiting or being processed/transmitted grows without bound. Thus, it is essential to know the constraints on offered load that guarantee stability, and hence that the network operates within its capacity.

Stability of Markov chains is traditionally studied through the Lyapunov test function approach; however, it is usually hard to construct a good test function in the multidimensional case.

Realizing that, Szpankowski devised a new method for finding stability regions in multidimensional distributed systems. He based his method on a non-Markovian technique combined with stochastic monotonicity and mathematical induction. This allowed him to find stability regions for such important networks as the token passing ring, ALOHA-type systems and others.

Algorithms are at the heart of virtually all computing technologies. Applications range from the infrastructure of computing (e.g., ordering a set of numbers) to highly complex systems (e.g., DNA sequencing). Clearly, the significance of algorithmics can hardly be overstated. Advances take the form of:

• Evaluating the performance of existing algorithms so as to perfect our understanding, and to better inform the choices that need to be made among alternative algorithms.
• Creating algorithms for new applications.
• Expanding the methodology of algorithm design and analysis. Szpankowski made tangible contributions in all three areas. He developed combinatorial and asymptotic methods that allow the classification of data structures into broad categories that are amenable to a unified treatment. These developments have two important consequences for the analysis of algorithms:
• It becomes possible to predict average behavior under more general probabilistic models.
• It becomes possible to analyze more structurally complex systems such as suffix trees and digital trees, the most popular data structures on words.

With respect to new methodology, Szpankowski, with Philippe Jacquet, developed a radically new method of analytic depoissonization to investigate sophisticated algorithms. Furthermore, in his recent work with Michael Drmota, the most popular algorithm design technique known as divide-and-conquer was given a solid mathematical foundation.

Source coding is an area of information theory that provides the foundation for data compression, which is in current widespread use in multimedia compression schemes. A solid understanding of the performance of compression schemes is a key tool in designing provably better information systems.

In information theory, by solving some longstanding open problems (e.g., Wyner-Ziv conjecture, Ziv’s conjecture, redundancy of Lempel-Ziv’78 algorithm, Gutman-Steinberg’s conjecture, Huffman’s and Khodak’s codes redundancy, Csiszar-Shields renewal process redundancy, entropy of hidden Markov processes and capacity of the noisy constrained channel) Szpankowski initiated a novel program, called analytic information theory, that applies analytic combinatorics to the foundation of information theory.

Following Hadamard’s precept, Szpankowski studied information theory problems using techniques of complex analysis such as generating functions, combinatorial calculus, Rice’s formula, Mellin transform, Fourier and Dirichlet series, saddle point methods, analytic poissonization and depoissonization, and singularity analysis.