SEMINARS AND EVENTS IN WINTER AND SPRING QUARTERS 2001.

1. Alan Mishchenko - Implicit Exact and Heuristic Sum-of-Product Minimization. February 9.
   
   ABSTRACT.
   
   Two-level sum-of-product (SOP) minimization is a classical problem arising in several fields of computer science, in particular, in logic synthesis and automated reasoning. Because of its importance, SOP minimization has attracted researchers' attention since 1950's. In 1994, O. Coudert proposed an implicit exact SOP minimization procedure, which proved to be much faster than explicit implementation in Espresso. The talk introduces the implicit representation of SOPs, summarizes the research contributions of the last decade, and discusses a novel implicit method for heuristic SOP minimization. Experimental results compare the performance of explicit vs. implicit, and exact vs. heuristic methods.
   
   About the speaker:
   
   Alan Mishchenko graduated with honors from Moscow Institute for Physics and Technology, Moscow, Russia (1993), and received his Ph.D. in Computer Science from Glushkov Institute of Cybernetics, Kiev, Ukraine (1997). Since 1998, he has been a visiting scientist and an Intel sponsored researcher at PSU. Alan's research interests include formal methods of logic synthesis and verification, CAD tools, decision diagrams and their applications, and EXOR logic.
   
   
2. Marek Perkowski - Multiple-Valued Reversible Logic, February 16.
   
   ABSTRACT.
   
   It was proven by Landauer that the necessary condition for a logic circuit to not dissipate energy is that the every gate in the circuit is reversible. (one-to-one mapping between inputs and outputs). This leads to the development of (binary) Reversible Logic realized in Quantum, Optical, CMOS and Nano technologies. Recently, two papers have been published that present generalization of binary reversible logic to Multi-valued logic, based on a very simple SOP-like realization and simple gates, thus a new area of multi-valued reversible logic has been started. In this lecture a new general Multiple-Valued Reversible logic with gates that are equivalents of all well-known reversible (quantum) binary gates (Feynman, Fredkin, Toffoli, Margolus, De Vos, Kerntopf gates, etc) will be presented. It will be shown that this is potentially a very fruitful research area, since many results can be generalized by analogy from binary reversible logic and standard multi-valued logic.
   
   About the speaker:
   
   Marek Perkowski is a Professor of Electrical and Computer Engineering at PSU. Since 1976 he has been working on reasoning by analogy, since 1985 on EXOR logic, and since 1994 on constructive induction approach to Data Mining and Machine Learning based on multiple-valued relation decomposition. These interests brought him to two new related research areas: reversible and quantum logic, and learning humanoid robots. His other research interests are in affective computing and "emotional talking heads".
   
   
   
   
3. Marek Perkowski - Multiple-Valued Reversible Logic, February 23.
   
   ABSTRACT. This is a continuation of the previous lecture. Many open problems will be presented.
   
   
4. Andie Al-Rabadi - Three-Dimensional Lattices based on new generalizations of Shannon and Davio expansions in Galois Logic. March 2.
   
   About the speaker:
   
   Andie (Anas) Al-Rabadi is a Ph.D. student at ECE PSU. He is the author of three papers and his interests are in Test, Logic Synthesis, humanoid intelligent robots, computer vision, and inductive Machine Learning.
   
   ABSTRACT
   
   The classical binary (Kronecker and Pseudo-Kronecker) Lattice Diagrams are based on Shannon, Positive Davio and Negative Davio expansions. In this work Shannon Expansion is generalized to a large family of expansions in multiple-valued logic, and Davio expansions are generalized using Galois Fields. The concept of three-dimensional lattices has been introduced together with joining operations that combine three nodes and propagate several correction functions. As far as we know, this is the first work ever devoted to "logic synthesis for layout" in three dimensions. As binary lattices, it can be used for self-test and self-repair, but first a physical process must be invented that will allow realization of truly three-dimensional circuits.
   
   
   
   
5. Garrison W. Greenwood - On the Use of Biologically-Inspired Adaptive Mutations to Evolve Artificial Neural Network Structures, March 9.
   
   About the speaker:
   
   Dr. Greenwood has twenty-five years of engineering experience in both industrial and academic environments. His industrial engineering employment as included the federal government (Department of the Navy), major aerospace companies (Boeing, Inc.), mid-size commercial companies (Honeywell, Eldec, SpaceLabs Medical) and 10-person startups (Voice Computer Corp.). This work has primarily involved the hardware design of multiprocessor embedded systems. Over the past eight years Dr. Greenwood has become a recognized specialist in the theory and application of evolutionary algorithms, having published over 40 peer-reviewed papers during that time period. He is currently serving as associate editor for the IEEE Transactions on Evolutionary Computation. Dr. Greenwood is a member of Tau Beta Pi, Eta Kappa Nu, Sigma Xi, and is a senior member of the IEEE. He is a licensed professional engineer in the state of California.
   
   ABSTRACT
   
   Evolutionary algorithms have been used to successfully evolve artificial neural network structures. Normally the evolutionary algorithm has several different "mutation operators" available to randomly change the number and location of neurons or connections. The scope of any mutation is typically limited by a user-selected parameter. Nature, however, controls the total number of neurons and synaptic connections in more predictable ways, which suggests the methods typically used by evolutionary algorithms may be inefficient. In this talk I describe a simple evolutionary algorithm that adaptively mutates the network structure where the adaptation method emulates neuron and synaptic growth in the rhesus monkey. Preliminary results indicate it is possible to evolve relatively sparse connected networks that exhibit quite reasonable performance.
   
   
   
   
6. Andy Fraser - Complexity: Sublime or Silly? March 16.
   
   ABSTRACT
   
   I will skeptically describe three related approaches to quantifying complexity that are associated with Boltzmann, Kolmogorov, and Rissanen. The ideas have been used to forecast the fate of the universe, to establish limits on the performance of engines, communication systems, and computers, and to guide statistical estimation. The ideas are intriguing and annoying; for example, the number Chaitin calls Omega is so "complex" that it's value is impossible to know.
   
   About the speaker:
   
   Andy Fraser has been at PSU since 1989 where he has appointments in both Systems Science and Electrical and Computer Engineering. He is interested in information theory and dynamics. He earned a PhD in physics at the University of Texas at Austin in 1988. Before entering graduate school, he designed integrated circuits at Fairchild Semiconductor.
   
   ON MARCH 23 the MEETING IS CANCELLED - WEEK OF FINALS.
   
   
   
   ON MARCH 30 the MEETING IS CANCELLED - SPRING BREAK.
   
   
   
   
   
   
7. James Mc Names - Spectrograms & Scaleograms for Biomedical Signal Analysis, April 6.
   
   ABSTRACT
   
   The spectrogram and scaleogram are methods of estimating the spectral content of non-stationary signals. These methods offer a number of important and complimentary insights that could not be gained by visual inspection of the signal alone. In this talk I will discuss some of the research projects undertaken by the Biomedical Signal Processing lab (bsp.pdx.edu) and explain some of the insights gained by these methods of analysis.
   
   
   
   About the speaker:
   
   James McNames is an assistant professor of electrical and computer engineering at Portland State University. He received his B.S. degree in electrical engineering from California Polytechnic State University, San Luis Obispo, in 1992. He received his M.S. and Ph.D. degrees in electrical engineering from Stanford University in 1995 and 1999, respectively. His primary research interests are biomedical signal processing, nonlinear modeling, and time series prediction.
8. Michael Levy - Using functional decomposition for control of gaits of a walking hexapod. Monday April 9. 12:30 pm - 1:30 pm.
   
   ROOM 6006, FAB building
   
   ABSTRACT
   
   The lecture will cover how servos are controlled, and some of the pitfalls of servo driven robotic applications. the lecture/seminar will be very informal. There will be a demonstration of the hexapod, a walk through of our microcontroller's current design, and a question and answer period.
   
   About the speaker:
   
   Michael Levy is a recent graduate of Portland State University (B.S. '01). For the last four months Michael has been working on the topic of 'gait generation' for a hexapod robot. Michael's primary interest is in neuromorpic engineering.
   
   
9. Bart Massey - New algorithms for Satisfiability, April 13.
   
   ABSTRACT
   
   Because of the generality and expressive power of CNF propositional formulae in problem modeling, good algorithms and heuristics for finding satisfying assignments (SAT) are important. In the past 10 years, a great deal of progress has been made in this area on several fronts. In this talk I will discuss SAT problem classes, improved heuristics for Davis-Putnam, stochastic ``local search'' methods, Relevance Bounded Learning, and the recent ``heavy tail'' results of Gomes and Selman.
   
   About the speaker:
   
   Bart Massey is an Assistant Professor of Computer Science at Portland State University, specializing in combinatorial search algorithms and applications in planning and scheduling. Bart also participates in the Oregon Master of Software Engineering program, has interests in programming languages and tools, and pursues such side interests as cryptography and robotics. Bart's doctoral work was at the University of Oregon Computational Intelligence Research Laboratory (CIRL), one of the principal locations for modern work on satisfiability and related search techniques.
   
   
   
10. Alan Mishchenko - Practical Application of Satisfiability in Logic Design. April 20.
    
    ABSTRACT
    
    Alan will discuss some problems from real life applications (logic design) that can be solved using satisfiability. Let us disscuss the opportunities of new algorithms for this kind of applications and brainstorm together how these problems, related to new FPGAs, can be solved.
    
    
11. H. Jin (Synopsys) Model Reduction in Formal Verification, April 27.
    
    ABSTRACT
    
    Model reduction is a crucial process for the success of formal verification. we present a model reduction algorithm for property checking. For the property to be verified, we first construct a property dependency graph which represents the function dependency of the property on variables. Beginning from the set of state variables appearing in the property, we search through the property dependency graph and add a noncorrelated set of stste variables to current set of state variables to construct a more detailed model at each reduction iteration step. The final reduced model is the one which is constructed by using all state variables that can be reached in the graph. The final reduced model the property weakly. Our reduction in MDG (Multiway Decision Graph) model checker due to the presence of abstract state variables, all backward reduction algorithms cannot be used in MDG. Our method is suitable for MDG and has been implemented in this tool, however, it can be used in other tools as well. We then discuss a quite common circuit structure which appears in telecommunication and data processing circuits. We use three verification tools MDG, FormalCheck and SMV to verify this circuit. The experimental results show that our reduction algorithm is more efficient on these typical structures.
    
    Speaker: Dr. H. Jin (Synopsys)
    
    Dr. Jin received her Ph.D. degree in Computer Science from University of Montreal, Canada, in 2000. She is a techincal staff of formal verification in Synopsys, Oregon.
    
    
12. Alan Mishchenko - Implicit Exact and Heuristic Sum-of-Product Minimization. May 4.
    
    ABSTRACT Continuation of the talk by this author from January. New results. Alan wrote the best SOP minimizer in the world.
    
    
13. Martin Zwick Reconstructability Analysis - New Problems and Solutions. May 11.
    
    ABSTRACT
    
    Reconstructability Analysis (RA) is a very general method developed within the systems community for modeling multivariate nominal data (where variables have states which are not ordered), or quantitative data which has been binned (discretized). It overlaps significantly with techniques used for machine learning and multivalued logic design, and also with statistical techniques used in the social sciences known as log-linear methods. RA is useful for modeling relationships which are nonlinear or have many-variable interaction effects. In this talk, I will review the basic ideas of RA, and summarize the work on implementations and new approaches to RA currently going on at PSU. This will include "state-based modeling", an approach more powerful than standard "variable-based" RA, efforts to include decision-theoretic (utility) considerations within RA, and new computational algorithms for RA implementation (including possible Fourier and BDD approaches).
    
    
    
    About the speaker:
    
    Martin Zwick is a Professor of Systems Science at PSU. His current research interests are reconstructability analysis for modeling and data mining, cellular automata and genetic algorithms, and the evolution of cooperation (artificial life/theoretical biology).
    
    
    
    
14. Garrison Greenwood, Ph.D., P.E. Overview of Quantum Computing. May 18.
    
    
    
    ABSTRACT Almost twenty years ago the Nobel Prize winning physicist Richard Feynman observed that classical computers could not simulate certain quantum mechanical effects. This observation spawned interest in the field of quantum computing?i.e., computational machines that perform calculations by emulating quantum mechanic effects. Although no practical quantum computer has yet been built (and the likelihood of building one in the near future is bleak), the interest in this field has not diminished because of the enormous computational potential such a machine can provide.
    
    This talk provides a basic overview of quantum computing. A description of the Shor quantum algorithm and the difficulties associated with constructing an operating quantum computer is discussed. The material covered should be comprehensible to listeners who have completed a formal class in quantum mechanics.
    
    
    
    About the speaker:
    
    Dr. Greenwood has twenty-five years of engineering experience in both industrial and academic environments. His industrial engineering employment as included the federal government (Department of the Navy), major aerospace companies (Boeing, Inc.), mid-size commercial companies (Honeywell, Eldec, SpaceLabs Medical) and 10-person startups (Voice Computer Corp.). This work has primarily involved the hardware design of multiprocessor embedded systems.
    
    Over the past eight years Dr. Greenwood has become a recognized specialist in the theory and application of evolutionary algorithms, having published over 40 peer-reviewed papers during that time period. He is currently serving as associate editor for the IEEE Transactions on Evolutionary Computation. Dr. Greenwood is a member of Tau Beta Pi, Eta Kappa Nu, Sigma Xi, and is a senior member of the IEEE. He is a licensed professional engineer in the state of California.
    
    
15. Anas Al-Rabadi, Introduction to Quantum Computing. May 25.
    
    
    
    ABSTRACT This is a short overview of the first three chapters of the textbook "Introduction to Quantum Computing" with emphasis on Hamiltonians.
    
    About the speaker:
    
    Anas Al-Rabadi works on his Ph.D. in Quantum Computing. He is the author of several papers.
    
    
16. Alan Coppola, Ph.D. Island Style FPGA Introduction, Architectural Modeling Toolkit, Routing Segmentation Study, Thoughts on Reversible Programmable Gate Arrays. June 8.
    
    
    
    ABSTRACT
    
    This talk will present an introduction to the standard Island Style FPGA architecture, along with how to design new architectures by creating an Architectural Modeling Toolkit(AMT). A sample Routing Segmentation Study is presented as an example of using the AMT. Finally, we close with some ideas on how FPGA architecture tools can be used to design Reversible Programmable Gate Arrays.
    
    About the speaker:
    
    Alan Coppola works for Cypress Semiconductor, on their next generation of programmable logic.