*CSEE Research Review - Talk Abstracts * *Friday, May 4, 2007* * * *Department of Computer Science and Electrical Engineering* *University** of Maryland, Baltimore County (UMBC)* * * *Session I*** Samuel J. Lomonaco, Jr. *A 3-Stranded Quantum Algorithm for the Jones Polynomial* In this talk, we describe a new quantum algorithm, called the /3-Stranded Braid (3SB)/ algorithm, created by Kauffman and Lomonaco, for computing the values of the Jones polynomial (a well known knot invariant) on the unit circle in the complex plane. This is a different algorithm from the recent one created by Aharonov, Jones, and Landau. But why are quantum computing researchers interested in the Jones polynomial? The reason is that one of the most pressing research problems in this field is to determine the actual limits of quantum computing. Will future quantum computers be general-purpose or special-purpose devices? Since the Jones polynomial is known to be #/P/-hard, it provides a useful tool for probing theses computational boundaries. This talk will begin with a brief introduction to the Jones polynomial. Next, a description of the 3SB quantum algorithm will be given. This will be followed by a description of a recent physical implementation of the 3SB algorithm using /Nuclear Magnetic Resonance (NMR)./ The talk will end with a discussion of computational complexity issues. Yung-Jui (Ray) Chen, /Photonics Technology Lab/ *Planar Lightwave Circuit Based ROADM/WSS* /Reconfigurable Optical Add-Drop Multiplexers (ROADM)/ and /Wavelength Selective Switches (WSS)/ are key network elements in intelligent networks. /Planar Lightwave Circuits (PLC)/ play an essential role in providing either integrated or hybrid solutions. We will examine the tradeoffs and challenges between monolithically integrated and hybrid systems. The impressive performance of photonics Moore's law in the last decade is mainly due to the advancement of /Dense Wavelength Division Multiplexing (DWDM)./ Network capacity expands readily by adding more wavelengths (channels). As network traffic and/or architecture grow complex, managing the wavelengths becomes a key network operation. ROADMs and WSS are devices that provide these vital network functions. Although data traffic has long surpassed the voice traffic, most current networks are still based on point-to-point architectures. The design and functionality of most current ROADM devices reflect this fact. To serve data-centric and mesh-topology future networks, advanced wavelength selective ROADMs and optical cross-connects (of which, WSS is the key building block) are needed. PLCs, which are a robust, highly integrated and volume-production technology, will play an essential role in building these advanced devices. There are three key building blocks in a wavelength selective ROADM/WSS: WDM multiplexer/de-multiplexer, optical switch fabric and optical signal conditioning/monitoring circuits. PLC technology performs well in all three areas. Other technologies also offer strong competitions in specific areas. In this talk we will examine different aspects and design considerations of implementing these building blocks by PLC technology. We will address the tradeoffs and challenges between monolithically integrated PLC solutions and hybrid solutions (either by integrating PLC parts only or PLC plus other technologies). Time Oates, /CORAL/ *On the Relationship between Lexical Semantics and Syntax for Grammar Induction* * * The ease with which human children learn their native language belies the complexity of that task. Chomsky introduced a hierarchy of formal languages that, to varying degrees, capture some of the complexity of the syntax of natural languages. But none of the classes of formal languages in that hierarchy, including the widely studied context-free languages, can be identified in the limit from positive examples (/i.e.,/ sentences that are in the language to be learned). Identifiability results for formal languages ignore a potentially powerful source of information available to learners of natural languages, namely, meanings. In this talk, I will explore learnability of syntax (/i.e.,/ context-free grammars) given positive examples and knowledge of lexical semantics, and the learnability of lexical semantics given knowledge of syntax. The long-term goal is to develop an approach to learning both syntax and semantics that bootstraps itself, using limited knowledge about syntax to infer additional knowledge about semantics, and limited knowledge about semantics to infer additional knowledge about syntax. * * *Session II*** Marc Olano, /VANGOGH Lab/ *Programming Graphics Hardware* The concept of creating user-programmable graphics hardware was developed by Dr. Olano in the 1990's on the PixelFlow machine developed at the University of North Carolina. Now it is present in the graphics hardware built into every PC and game system sold, and is a required feature of the newest Windows operating system. As it has become more common to be able to program graphics hardware, the research question has moved from how to make it programmable to what to do with the powerful parallel processing capabilities. Dr. Olano will present results of two recent research projects. One uses graphics hardware programmability to provide interactive simulation of translucent materials by casting rays through a volume density field within the translucent object. The results run at 12-300 frames per second, depending on hardware and quality settings, allowing interactive rendering of materials not possible with previous techniques. The second application uses the same hardware as a general parallel processor for a non-graphics application, multidimensional scaling to find a lower-dimensional representation of a high-dimensional dataset. We can reach convergence on a dataset with 100,000 points in 20 seconds. Many classic algorithms cannot handle datasets of this size, and one of the fastest alternatives, Landmark MDS, takes 6 minutes in our CPU benchmark tests. Anupam Joshi, /Ebiquity/ *Trust, Influence, and Bias in the Blogosphere* The role of social networks has been well explored in understanding how communities and individuals spread influence. In a densely connected world where much of our communication happens online, social media and networks have a great potential in influencing our thoughts and actions. We describe techniques to find "like-minded" blogs based on blog-to-blog link sentiment for a particular domain. Using simple sentiment detection techniques, we identify the polarity (positive, negative or neutral) of the text surrounding links that point from one blog post to another. We use trust propagation models to spread this sentiment from a subset of connected blogs to other blogs and deduce likeminded blogs in the blog graph. Our results confirm that the simple heuristics for analysis of text surrounding links and generation of missing polar links (links with positive or negative sentiment) using trust propagation is highly applicable for domains having weak link structure. These techniques demonstrate the potential of using polar links for more generic problems such as detecting trustworthy nodes in web graphs. Jonathan Bronson (Advisor: Rheingans) - /Award for Best Research by an MS Student/ *Automated Stencils and Gobos from 3D Models* Stencils are widely used as templates for easy reproduction of common symbols and images, as well as in the production of street art. In theatrical lighting, stencils known as gobos, templates, or cookies are placed in the light path to cast shadows. Due to the physical constraints for stencils to remain connected, it can be difficult to create visually pleasing results for complicated imagery. We present a method for generating expressive stencils from arbitrary 3D models. Users provide input geometry and can interactively adjust desired view, line thicknesses, and lighting to achieve their final desired stencil. Stencil connections are then automatically chosen in a few seconds in a manner which will cause the least amount of destruction to the image while satisfying physical connectivity constraints. The final stencils can be used digitally or physically fabricated for personal or business use. A well done fabrication can produce theatrical gobos used for complex stage lighting effects. We demonstrate virtual stencil images, physical stencils used with spray paint, and custom lighting gobos created from our stencil images. *Session III*** * * James Plusquellic, /VLSI Research Group/ *Challenges and Solutions to Screening Defective Chips in Nanometer Technologies* As silicon technology moves deeper into the nanometer domain, defect screening methods such as/ supply current Quiescent (IDDQ/) are becoming less effective. This is acknowledged in the Test and Test Equipment "Screening for Reliability" section of /The International Technology Roadmap for Semiconductors/ /(//ITRS),/ 2005 edition. Trends in background leakage currents have severely challenged the use of IDDQ testing methods. It is generally believed that IDDQ testing, as it is currently practiced, is considered "dead" for all practical purposes beginning with the 90 nm node. We believe the only way to extend the life of IDDQ is to adopt the methods that we propose. The novelty of our proposed methods lies in the measurement and joint analysis of multiple power port signals. The power grids of many digital and /System-on-a-Chip (SoC)/ chips are interfaced to the external power supplies through multiple supply ports as a means of meeting the power requirements of the chip. We leverage this characteristic as a means of improving the resolution to small changes in a chip's power signals caused by the activation of a defect. By measuring signals locally and at multiple places in the two dimensional plane of the /Integrated Circuit (IC),/ the wash-out effects that occur when the power grid signals are measured globally are mitigated. Our method, called /Quiescent-Signal Analysis (QSA)/, exploits this type of measurement scheme: (1) to increase the ratio of defect current to leakage current for the detection of defects, and (2) to obtain spatial information about the physical location of the defect. In this talk, I present the results of applying QSA to a set of test chips fabricated in a 10 metal layer, 65 nm technology. The analysis demonstrates that it is possible to increase the sensitivity of IDDQ for detecting defects by almost an order of magnitude over existing techniques. It is also shown that the defect localization method is able to locate a defect to a physical location in the layout with a error of less than 10 microns in most cases. Tulay Adali, /Machine Learning for Signal Processing Laboratory/ *Independent Component Analysis of Brain Imaging Data* /Independent Component Analysis (ICA)/ has emerged as an attractive analysis tool for discovering hidden factors in observed data and has been successfully applied for data analysis in a wide array of applications. A very promising application domain for ICA has been the study of brain function using medical imaging data. In this talk, I will first introduce ICA of medical imaging data and then will present some examples from our own work. Sandor Dornbush (Advisor: Anupam Joshi), /eBiquity/ -- /Award for Best Research by a PhD Student/ *XPod: A Human Activity Aware Learning Mobile Music Player * The XPod system, presented in this paper, aims to integrate awareness of human activity and musical preferences to produce an adaptive system that plays the contextually correct music. The XPod project introduces a "smart" music player that learns its user's preferences and activity, and tailors its music selections accordingly. We are using a BodyMedia device that has been shown to accurately measure a user's physiological state. The device is able to monitor a number of variables to determine its user's levels of activity, motion and physical state so that it may predict what music is appropriate at that point. The XPod user trains the player to understand what music is preferred and under what conditions. After training, the XPod, using various machine-learning techniques, is able to predict the desirability of a song, given the user's physical state. We are currently exploring using Nokia 5500 Sport phones to build context aware music players. These phones have accelerometers and other sensors for determining a users context. We hope to have demonstration devices ready in time for the research review.