2002-2003 AbstractsCPSC 681 Graduate Seminar:Challenges in Quantum ComputingAndreas Klappenecker, Assistant Professor, CS Department, Texas A&M University
4:10pm, Wednesday September 18, 2002 AbstractA quantum computer encodes, stores, and manipulates information, just like a classical computer. The basic operations are easy to understand. Yet some of the algorithmic consequences are surprising. We give an introduction to a number of solved and unsolved problems in quantum computing, and discuss some challenges.BiographyAndreas Klappenecker is an Assistant Professor in Computer Science at Texas A&M University. He received his Ph.D. in 1998 from the University of Karlsruhe. Dr. Klappenecker organized the Mini-Symposium on Quantum Computing in 2001. His research interests are in the areas of quantum computing, image processing, and cryptography.Faculty Contact: Riccardo Bettati (bettati@cs.tamu.edu)
CPSC 681 Graduate Seminar:Standard-Library Exception SafetyBjarne Stroustrup, CoE Endowed Chair in Computer Science, CS Department, Texas A&M University / AT&T Labs - Research
4:10pm, Wednesday October 2, 2002 AbstractDesigning containers and algorithms that are simultaneously efficient and exception safe is hard. The C++ standard library was designed to meet this challenge. This talk presents the guarantees offered by the standard, the requirements on user code that these requirements depend on, and explains the reasons behind the tradeoffs. Examples from a standard-library vector implementation are used to illustrate general techniques. As ever, the standard library provides examples of widely applicable techniques and principles.BiographyBjarne Stroustrup is the designer and original implementer of C++. Over the last decade, C++ has become the most widely used language supporting object-oriented programming by making abstraction techniques affordable and manageable for mainstream projects. Using C++ as his tool, Stroustrup has pioneered the use of object-oriented and generic programming techniques in application areas where efficiency is a premium; examples include general systems programming, switching, simulation, graphics, user-interfaces, embedded systems, and scientific computation.His book "The C++ Programming Language" (Addison-Wesley, 1st edition 1985, 2nd edition 1991, 3rd edition 1997, "special" edition 2000) is the most widely read book of its kind and has been translated into 18 languages. A later book, "The Design and Evolution of C++" (Addison-Wesley, 1994) broke new ground in the description of the way a programming language was shaped by ideas, ideals, problems, and practical constraints. In addition to his five books, Stroustrup has published more than eighty academic and more popular papers. He took an active role in the creation of the ANSI/ISO standard for C++. Born in Aarhus, Denmark, Bjarne Stroustrup received his Cand. Scient. degree (Mathematics and Computer Science) in 1975 from the University of Aarhus Denmark, and his Ph.D. (Computer Science) in 1979 from Cambridge University, England. Before joining Texas A&M's computer science faculty on a full-time basis in January, 2003, Stroustrup will remain head of AT&T Lab's Large-scale Programming Research department. Stroustrup is an AT&T Bell Laboratories Fellow, an AT&T Fellow an Association for Computing Machinery (ACM) Fellow. He received the 1993 ACM Grace Murray Hopper award for his early work on C++. Faculty Contact: Riccardo Bettati (bettati@cs.tamu.edu)
CPSC 681 Graduate Seminar:Adaptive Scalable Internet StreamingDmitri Loguinov, Assistant Professor, CS Department, Texas A&M University
4:10pm, Wednesday October 9, 2002 AbstractTypically, NACK-based congestion control is dismissed as being not viable due to the common notion that "open-loop" congestion control is simply "difficult." Emerging real- time streaming applications, however, often rely on rate-based flow control and would benefit greatly from scalable NACK-based congestion control. This talk sheds new light on the performance of NACK-based congestion control and measures the amount of "difficulty" inherently present in such protocols. We specifically focus on increase- decrease (I-D) congestion control methods for real-time, rate-based streaming. First, we introduce and study several new performance measures that can be used to analyze the class of general I-D congestion control methods. These measures include monotonicity of convergence to fairness and packet-loss scalability. Second, under the assumptions that the only feedback from the network is packet loss, we show that AIMD is the only TCP-friendly method with monotonic convergence to fairness. Furthermore, we find that AIMD possesses the best packet-loss scalability among all TCP-friendly binomial schemes and show how poorly all of the existing methods scale as the number of flows is increased. Third, we show that if the flows can obtain the knowledge of an additional network parameter (i.e., the bottleneck bandwidth), the scalability of AIMD can be substantially improved. We conclude the talk by studying the performance of a new scheme, called Ideally-Scalable Congestion Control (ISCC), both in simulation and a NACK-based MPEG-4 streaming application over a Cisco testbed.BiographyDmitri Loguinov is an assistant professor in the Department of Computer Science at Texas A&M University. He received his B.S. (with honors) in Computer Science from Moscow State University in 1995. Subsequently, Dr. Loguinov worked on his Master's degree in the area of networking protocols and real-time streaming at Kansas State University and The City College of New York. In 1997, he transferred into the Ph.D. program of The City University of New York and continued his research in the area of networking. Starting in 1998, Dmitri Loguinov's Ph.D. was supported by a series of annual grants from Philips Research, USA. His work at Philips involved performance analysis of MPEG-4 real-time streaming, congestion control for real-time traffic, Internet traffic measurements, analysis, and modeling.Faculty Contact: Riccardo Bettati (bettati@cs.tamu.edu)
CPSC 681 Graduate Seminar:Network Elements Based on Partial StateA.L. Narasimha Reddy, Associate Professor, Department of Electrical Engineering, Texas A&M University
4:10pm, Wednesday October 16, 2002 AbstractIn this talk, we propose network elements based on partial state which employ a limited fixed amount of memory. The state may be organized as a hardware cache or a hash-based memory. The amount of employed state is not proportional to the number of flows passing through the network element. The limited amount of state can be efficiently managed to capture the significant or dominant flows in the traffic thus maximizing the utility of the state. This is based on the fact that current Internet traffic is heterogeneous where a limited number of flows contribute to a large fraction of the link utilization.We will show that the partial state network elements allow effective resource management to (a) ease congestion at times of high load, (b) contain Denial of Service attacks on network infrastructure, and (c) allow fairer distribution of network resources. We will also show that state management policies can be designed to differentiate between responsive and nonresponsive flows and hence facilitate better treatment for responsive flows. We will also show that the proposed architectures can significantly improve performance of "web mice" flows. We will report on our experience and results in building a partial-state router based on a Linux-PC. BiographyA. L. Narasimha Reddy received his B.Tech. degree in Electronics and Electrical Engineering from the Indian Institute of Technology, Kharagpur, India, in August 1985, and the M.S. and Ph.D. degrees in Computer Engineering from the University of Illinois at Urbana-Champaign in May 1987 and August 1990 respectively. At Illinois, he was supported by an IBM Fellowship. He is currently an Associate Professor in the department of Electrical Engineering at Texas A & M University. He was a Research Staff Member at IBM Almaden Research Center in San Jose from Aug. 1990- Aug. 1995. Reddy's research interests are in Multimedia, I/O systems, Network QOS and Computer Architecture. Currently, he is leading projects on building scalable multimedia storage servers and partial-state based network elements. His group is also exploring various issues related to Network QOS. While at IBM, he coarchitected and designed a topology-independent routing chip operating at 100 MB/sec, designed a hierarchical storage management system and participated in the design of video servers and disk arrays. Reddy is a member of ACM SIGARCH and is a senior member of IEEE Computer Society. He has received an NSF CAREER award, and he received an Outstanding Professor award at Texas A & M.Faculty Contact: Riccardo Bettati (bettati@cs.tamu.edu)
CPSC 681 Graduate Seminar:A Self-organizing Model of Chemotopic Convergence for Olfactory CodingDr. Ricardo Gutierrez-Osuna, Assistant Professor, CS Department, Texas A&M University
4:10pm, Wednesday October 30, 2002 AbstractThis talk presents a self-organizing model of convergence for the early stages of the olfactory pathway. The model generates a chemotopic projection from olfactory receptor neurons onto glomeruli based on receptor affinity distributions. The resulting glomerular images reveal an olfactory code consistent with neurobiology, whereby odor quality is encoded by a unique spatial pattern across glomeruli, and odor concentration is related to the intensity and spread of this pattern. The model is also able to predict a broadening of the intensity tuning range of glomeruli.BiographyRicardo Gutierrez-Osuna received the B.S. degree in Electronics Engineering from the Polytechnic University of Madrid (Spain) in 1992, and the M.S. and Ph.D. degrees in Computer Engineering from North Carolina State University in 1995 and 1998, respectively. From 1998 to 2002, he was assistant professor of Computer Science and Engineering at Wright State University, Dayton, Ohio. Dr. Gutierrez-Osuna is a recipient of the National Science Foundation Career Award for his research on machine olfaction with gas sensors arrays. His research interests include intelligent systems, pattern recognition, biological cybernetics, bioinformatics, speech processing, sensor instrumentation and mobile robotics and embedded systems.Faculty Contact: Riccardo Bettati (bettati@cs.tamu.edu)
CPSC 681 Graduate Seminar:Super-Dense Servers: An Energy-efficient Approach to Large-scale Server ClustersCharles Lefurgy, Research Staff Member IBM Austin Research Lab
4:10pm, Wednesday November 6, 2002 AbstractPower-performance optimization is a relatively new problem area in the context of server clusters. At IBM Research in Austin, we have investigated the problem of designing a web server cluster that can be used in high-volume deployments that are limited by energy and cooling constraints. First we designed a cluster using a custom-designed Super Dense Server built from low-power components that are normally used in mobile systems. Second, we improved the energy-efficiency of the cluster further by developing software techniques for power-management. Energy is saved by powering-down some servers when the desired quality of service can be met with fewer servers.In the first half of this talk, I will describe the research prototype Super Dense Server. I will cover its hardware features, show how they challenge the operating system and middleware and describe the system software enhancements used to meet these challenges. The performance evaluation shows that dense servers are a viable deployment alternative for the edge and application servers commonly found in conventional web sites and large data centers. In the second half of the talk, I will describe a method of distributing web requests across the cluster so that energy can be saved at a small cost in performance. This will cover the common pitfalls in doing energy measurement studies, the modifications required to enable the power-aware request distribution, and results on the energy savings achieved. BiographyCharles Lefurgy is a Research Staff Member in the Power-Aware Systems group of the IBM Austin Research Lab. He joined IBM in 2000 and studies software strategies for low-energy computers. His other research interests include microarchitecture, memory systems and compilers. He holds BSE, MSE, and Ph.D. degrees in computer engineering from the University of Michigan. His dissertation work focused on compressed memory systems for embedded computing.Faculty Contact: Riccardo Bettati (bettati@cs.tamu.edu)
CPSC 681 Graduate Seminar:Internet-based Collaborative Computing and the REDUCE ProjectChengzheng Sun, Chair of Internet Computing, School of Computing & Information Technology, Griffith University, Australia
4:10pm, Wednesday November 13, 2002 AbstractInternet is at the core of the information revolution which changes the way we communicate, work, learn, do business, and play. A major trend is to use the Internet to enhance human-to-human interaction, communication, and collaboration. In this talk, I will first give an overview of the challenges in Internet-based collaborative computing systems. Then, my talk will focus on the major research issues, technical challenges, and innovative solutions in an ongoing research project -- REDUCE (REplicated Distributed Unconstrained Collaborative Environment), which aims to develop Internet-based collaborative technologies and applications for supporting geographically dispersed people to interact and collaborate over shared (text/graphics/hypertext/multimedia) document environments. A number of Internet-based prototype collaborative systems have been built to demonstrate the feasibility and usability of REDUCE technologies (publicly accessible at http://reduce.qpsf.edu.au). REDUCE technologies are being applied in Internet-based collaborative programming and software design, collaborative software version control, collaborative XML/HTML document design, collaborative word processing, and Internet-based multi-player games.For more details on the REDUCE program, please see:
BiographyDr Chengzheng Sun is a full Professor (Chair of Internet Computing) at the School of Computing & Information Technology, Griffith University, Brisbane, Australia. He obtained a PhD in computer engineering from National University of Defense Technology, China in 1987, and a PhD in computer science from the University of Amsterdam, Netherlands in 1992. He worked as a researcher and a senior software engineer for over five years in the European computer industry (Philipes Research Labs Eindhoven and ACE Amsterdam), accumulating substantial experiences in the design and implementation of research and commercial distributed computing systems. Since June 1993, he has been working with Griffith University. His major areas of expertise and research interests include: Internet and computing technologies and applications; collaborative systems and CSCW (Computer-Supported Cooperative Work); distributed operating systems and computer networks; mobile computing systems; and parallel implementation of object-oriented and logic programming languages. He has published over 120 papers in international journals and conferences in his areas of research. Professor Sun has been leading the REDUCE research program (funded by Australian Research Council) since 1994.Faculty Contact: Riccardo Bettati (bettati@cs.tamu.edu)
CPSC 681 Graduate Seminar:The K42 Research Operating SystemOrran Krieger, Manager of the Advanced Operating System Research Team at IBM T.J. Watson Research Center
4:10pm, Wednesday November 20, 2002 AbstractK42 is a new Linux-compatible research operating system kernel for 64-bit shared memory multiprocessors. Each virtual and physical resource, e.g., open file, memory region, page table, is managed by a separate object instance. This model provides the standard software engineering benefits (portability, maintainability, extensibility), but, more importantly: 1) allows customization on a resource by resource basis and 2) allows accesses to different resources to be efficiently handled in parallel. Individual objects can be "hot-swapped" with new implementations based on current or expected use and/or to selectively upgrade the system with bug, security, or performance fixes without bringing it down.We will give a brief overview of K42, describing some of the key technology and the newest performance and scalability results, and we will discuss where we are going with the system. One of the fundamental goals of this project has been to develop an operating system platform that not only has performance and functionality advantages over existing systems, but which can be used as a platform to more easily study research questions and then transfer technology into commercial systems like Linux. K42 is freely available to collaborators under a GPL license. We will discuss some of the success stories in technology already being transferred to Linux and then touch on a few of the interesting areas of research we would like to explore with the system (e.g., application directed customization, scalability, fault tolerance, virtualization, real-time, security...) BiographyOrran Krieger is the manager of the advanced operating system research team at IBM T.J. Watson Research Center. He received a BASc from the University of Ottawa in 1985, a MASc from the University of Toronto in 1989, and a PhD from the University of Toronto in 1994, all in Electrical and Computer Engineering. He was one of the main architects and developers of the Hurricane and Tornado operating systems at the University of Toronto, and was heavily involved in the architecture and development of the Hector and NUMAchine shared-memory multiprocessors. Currently, he is project lead on the K42 operating system project at IBM T.J. Watson Research Center, and an adjunct associate professor in computer science at CMU. His research interests include operating systems, file systems, and computer architecture.Faculty Contact: Riccardo Bettati (bettati@cs.tamu.edu)
CPSC 681 Graduate Seminar:Security Architectures RevisitedHermann Härtig, Professor for Operating Systems, Dresden University of Technology
4:10pm, Monday December 02, 2002 AbstractSecure operating systems need to have at least these properties:
The talk claims that the proper combination of
Faculty Contact: Riccardo Bettati (bettati@cs.tamu.edu)
CPSC 681 Graduate Seminar:Multipole-Based Hierarchical Techniques and Their ApplicationsVivek Sarin, Assistant Professor, CS Department, Texas A&M University
4:10pm, Monday February 03, 2003 AbstractThe talk will present multipole-based hierarchical approximation algorithms for the n-body problem. These techniques approximate the pairwise interactions of n particles in O(n) time only at the expense of modest decrease in accuracy. The talk will introduce a novel framework for such techniques and outline a parallel formulation. The talk will also discuss the use of these methods in a variety of applications including parasitic extraction of VLSI circuits, simulation of incompressible fluid flows, analysis of protein docking, and the study of laser ablation of nano particles.BiographyVivek Sarin is an Assistant Professor in Computer Science at Texas A&M University. He received his Ph.D. in 1997 from the University of Illinois. His research interests include numerical methods, parallel algorithms, and computational science.Faculty Contact: Thomas Ioerger (ioerger@cs.tamu.edu)
CPSC 681 Graduate Seminar:Traffic Simulation and Route Choice BehaviorDirk Helbing, Managing Director of the Institute for Economics and Traffic, Dresden University of Technology
4:10pm, Wednesday February 12, 2003 AbstractPhysical models and computer simulations have helped to understand many of the miracles of traffic flow: Why are vehicles sometimes stopped by so-called "phantom traffic jams," although they all like to drive fast? What are the mechanisms behind stop-and-go traffic? Why are there several different kinds of congestion, and how are they related? Why do most traffic jams occur considerably before the road capacity is reached? Can a temporary reduction of the traffic volume cause a lasting traffic jam? All of this is important to understand from the perspective of intelligent transportation systems. Surprisingly, speed limits can speed up traffic under certain conditions, and traffic lights at on-ramps can reduce the overall travel times. Driver assistance systems have a particularly high potential.Traffic forecasts are of similar complexity as weather forecasts, but drivers will react on them and thereby invalidate the forecasts. Recent decision experiments are testing strategies to solve this problem. In these day-to-day route choice experiments, the adaptivity ("group intelligence") with respect to changing environmental conditions and unreliable information is quite astonishing. Nevertheless, we find an intermittent dynamical reaction to aggregate information similar to volatility clustering in stock market data, which leads to considerable losses in the average payoffs. It turns out that the decision behavior is not just driven by the potential gains in payoffs. To understand these findings, one has to consider individual learning. Our results are highly significant for predicting decision behavior and reaching the optimal distribution of behaviors by means of decision support systems. These results are practically relevant for any information service provider, although the test persons were found to be more or less resistant against manipulation through biased information. Participants followed recommendations just as much as they helped them to reach their personal goals.
[1] D. Helbing (2001) "Traffic and related self-driven many-particle systems."
Reviews of Modern Physics 73, 1067-1141. BiographyDirk Helbing is the Managing Director of the Institute for Economics and Traffic at Dresden University of Technology, where he was appointed full professor in 2000. Having studied Physics and Mathematics in Göttingen, his master thesis dealt with the nonlinear modeling and multi-agent simulation of observed self-organization phenomena in pedestrian crowds. Two years later, he finished his Ph.D. in Stuttgart on modeling social interaction processes by means of game-theoretical approaches, stochastic methods and complex systems theory, which was awarded two research prizes. After having completed his habilitation on traffic dynamics and optimization in 1996, he received a Heisenberg scholarship. Both theses were printed by international publishers.Apart from this, Helbing has co-edited several proceedings of international conferences on cooperative dynamics in socio-economic and traffic systems that he co-organized. He has given 90 invited talks and published more than 100 papers, including several contributions to high-impact journals like Nature, Science, or Reviews of Modern Physics, which were discussed by the public media (newspapers, radio, and TV) more than 130 times. Moreover, he reviews for many interdisciplinary, physical, socio-economic, and transportation journals as well as science foundations (DFG, NSF). Helbing is also co-editor of the Traffic Forum, the Econophysics Forum, and the Internet Journal of Cooperative Transportation Dynamics. He collaborates closely with international scientists, since he worked, for example, at the Weizmann Institute in Israel, the Xerox PARC in the Silicon Valley, and the Collegium Budapest - Institute for Advanced Study in Hungary. Thanks to various multi-partner research projects, he also maintains good cooperation with the Volkswagen AG, the Siemens AG, the DaimlerChrysler AG, and other companies. Faculty Contact: Thomas Ioerger (ioerger@cs.tamu.edu)
CPSC 681 Graduate Seminar:Random Walk for Self-Stabilizing Group Communication in Ad-Hoc NetworksJennifer Welch, Professor, CS Department, Texas A&M University
4:10pm, Monday February 17, 2003 AbstractWe introduce a self-stabilizing group communication system for ad-hoc networks. The system design is based on random walks of mobile agents. Several settings for modeling the location of the processors in the ad-hoc network are presented. The group membership algorithm is based on collecting and distributing information via a mobile agent. The new techniques support group membership and multicast, and also support resource allocation.This is joint work with Shlomi Dolev and Elad Schiller from Ben-Gurion University of the Negev, Israel. BiographyJennifer L. Welch is a professor in the Department of Computer Science at Texas A&M University. She received her BA from the University of Texas at Austin, and her SM and PhD from the Massachusetts Institute of Technology. Her research interests include the theory of distributed computing, algorithm analysis, distributed systems, mobile ad hoc networks, and distributed data structures.Faculty Contact: Thomas Ioerger (ioerger@cs.tamu.edu)
CPSC 681 Graduate Seminar:The Pensieve Project: Compiling for Multiple Memory ModelsSamuel Midkiff, Associate Professor, Department of Electrical and Computer Engineering, Purdue University
4:10pm, Monday March 3, 2003 AbstractThe success of Java has caused hundreds of thousands of programmers to be introduced to the joys of parallel programming. Java is the most popular language ever to have attempted to unambiguously define the order that operations in one thread will appear to have occurred in another thread (the Java Memory Model), and has incorporated multithreading into common operations (e.g., responding to mouse input). The Java Memory Model is widely acknowledged to be a failure and has exposed the lack of practical experience designing usable memory models in the compiler and programming languages community. The Pensieve Project is an attempt to increase our practical knowledge of how to properly define a memory model by building an infrastructure for rapidly prototyping new memory models and testing their performance within a high performance Java virtual machine (the Jikes RVM). This talk will initially present an overview of software consistency (or memory) models and the issues involved, and then describe the Pensieve infrastructure, including representations and analyses within the compiler, the current state of the project (including some preliminary results), and future work and directions.BiographySam Midkiff is an Associate Professor in the Department of Electrical and Computer Engineering, Purdue University. He received his Ph.D. from the University of Illinois at Urbana-Champaign in 1992, and spent the next ten and one-half years at the IBM T.J. Watson Research Center in Yorktown Heights, New York, joining the faculty of the Purdue ECE Department in the fall of 2002. While at IBM he was a key member of the teams that developed the IBM xlHPF compiler, the Ninja (Numerically Intensive Java) system, and the Quicksilver quasi-static compiler. His current research interests include compiling for ease of use (including compiling for software and hardware consistency models) and compiling for low power.Faculty Contact: Lawrence Rauchwerger (rwerger@cs.tamu.edu)
CPSC 681 Graduate Seminar:High-Performance Web CrawlingMarc Najork, Researcher, Microsoft Research (MSR) Silicon Valley
4:10pm, Wednesday March 19, 2003 AbstractHigh-performance web crawlers are an important component of many web services. The design of such a crawler poses many challenges, both technical and social, primarily due to the large scale of the web. The crawler must be able to download pages at a very high rate, yet it must not overwhelm any particular web server. Moreover, it must maintain data structures far too large to fit in main memory, yet it must be able to access and update them efficiently. This talk describes Mercator, a distributed and very fast web crawler. Running on a four-machine cluster, Mercator is able to download 50 million web pages per day over a sustained period of time. Its flexible, component-based architecture makes it an ideal vehicle for web characterization research. Mercator is a core component of the AltaVista search engine, and has been used in a number of research projects.BiographyMarc Najork is a researcher at MSR Silicon Valley, Microsoft's fifth and newest research lab. His current research focuses on web crawling, web characterization, and distributed storage systems. He received his Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in 1994.Faculty Contact: Riccardo Bettati (bettati@cs.tamu.edu)
CPSC 681 Graduate Seminar:Building Adaptive Programs with Local Sensing of Execution ConditionsDimitris Nikolopoulos, Assistant Professor, Department of Computer Science, The College of William & Mary
4:10pm, Monday March 24, 2003 AbstractAlthough the research community recognizes that the vastness of networked computational resources opens up numerous exiting opportunities for computing, the techniques and protocols for using these resources to the benefit of both the resource providers and the resource users lag behind the vision. A major obstacle is the lack of software that enables adaptivity of programs to a very diverse variety of systems, with capacities and latencies that vary by orders of magnitude. Problems become even more complex if we consider that resources need to be shared between users with conflicting demands.This talk presents new software techniques for developing applications that adapt to non-dedicated memory hierarchies. We present novel approaches for adaptation, based solely on local sensing of execution conditions from within the program. Using this approach, adaptivity is not enforced by explicit communication with some authority (e.g., the 0S or a batch scheduler), but by having the program sample parameters of its local execution environment and extrapolate global execution conditions from these parameters. We present three techniques for adaptation of programs to non-dedicated memory hierarchies. The first technique, adaptive blocking, enables adaptation in blocked-structured codes that run on multithreaded processors with shared on-chip caches. The second technique, local paging with malleable memory mapping, enables adaptation and better memory management of the resident set of data-intensive programs in DRAMs with fluctuating utilization. The third technique, bandwidth-driven process control, enables adaptive control of parallelism on shared-memory multiprocessors whenever the bandwidth of the shared bus becomes a bottleneck. The talk discusses ideas for compiler and runtime support for adaptation and some applications of the proposed work in parallel, distributed and embedded computing. BiographyDimitris Nikolopoulos is an Assistant Professor of Computer Science at the College of William & Mary. Before joining William & Mary, he was a Visiting Assistant Professor of the Department of Electrical and Computer Engineering at the University of Illinois, Urbana-Champaign. He received his Ph.D. in Computer Engineering in 2000 and the Diploma in Computer Engineering in 1996, both from the University of Patras, Greece. His research focuses on the integration of system software components for effortless development of scalable and adaptive programs on high-end computing platforms. He has authored several papers in major conferences and journals in the area of HPC, including three papers that won Best Paper Awards.Faculty Contact: Nancy Amato (amato@cs.tamu.edu)
CPSC 681 Graduate Seminar:Parameterized SAT: Solving the Satisfiability Problem by the SliceStefan Szeider, Post-Doctoral Researcher, Department of Computer Science (Theory Group), University of Toronto
4:10pm, Wednesday March 26, 2003 AbstractThe framework of Parameterized Complexity, introduced by Downey and Fellows [1], provides a means for coping with computationally hard problems: It turned out that many intractable problems can be solved efficiently "by the slice"; that is, the required time is exponential in the parameter but polynomial in the size of the instance (the order of the polynomial does not depend on the parameter). Problems which allow solutions of this type are called fixed-parameter tractable (FPT) and have been found significant for practical applications.In the talk we will consider the parameterized complexity of the boolean satisfiability problem (SAT). We will present a new Davis-Logemann-Loveland type algorithm which allows efficient SAT decision for instances of bounded "maximum deficiency" (a parameter defined via graph matchings). We will compare maximum deficiency with known FPT parameterizations of SAT which are based on structural graph decompositions (treewidth, branchwidth, etc.). Finally we will deploy our new algorithm for showing fixed-parameter tractability of minimal unsatisfiable sets of clauses with bounded clause-variable difference (improving significantly upon known algorithms [2]). [1] Downey and Fellows, "Parameterized Complexity", Springer Verlag, New York, 1999. [2] Fleischner, Kullmann, Szeider, "Polynomial-Time Recognition of Minimal Unsatisfiable Formulas with Fixed Clause-Variable Difference", Theoretical Computer Science 289 no. 1, pp. 503-516, 2002. BiographyStefan Szeider is a post-doctoral researcher at the Department of Computer Science (Theory Group), University of Toronto. He graduated in Mathematical Logic and received his Ph.D. in Mathematics at the University of Vienna, Austria. His current research interests include complexity of algorithms, propositional proof complexity, graph theory, and parameterized complexity.Faculty Contact: Lawrence Rauchwerger (rwerger@cs.tamu.edu)
CPSC 681 Graduate Seminar:Leadership Roles for Today's High-Tech EngineersMike Perez, Vice President of Engineering and General Manager at Compaq Computer Corporation, retired
4:10pm, Wednesday April 16, 2003 AbstractAchieving long-term success in a highly competitive market such as the computer industry requires the continuous crisp execution of product plans to stay ahead of the competition. This can only be achieved by the creation of a continuous process to address customer needs in a timely manner and thus developing long-term customer loyalty. Excelling in this process is a particularly challenging task in times of increased competition, limited resources and shortened product life cycles. In this challenging environment, the role of the well-rounded engineer must go well beyond the traditional product development role. Today, engineers must be an integral part of a business team that continuously assesses the needs of customers, develops innovative technologies to address those needs and introduces those technologies into pragmatic product plans that deliver superior value to customers. This process involves continuous customer interaction, candid debate, and sometimes heart wrenching tradeoffs of available resources, schedule requirements, and product functionality, all based on what is right for the customer and the long-term success of the business. Mike discusses his experiences in this process and makes a case for the leadership roles that the well-rounded engineer must play in today's high-tech enterprises to enable long-term business success.BiographyMike Perez is a former Vice President of Engineering and General Manager at Compaq Computer Corporation. Mike joined Compaq in its early days in 1983 and was part of the engineering team that developed numerous portable and desktop products, including the industry first 386-based desktop product. As Vice President of Engineering, he was part of the team that launched Compaq's successful Server Division, later serving as General Manager of that Division. He also launched Compaq's Workstation Division as its first General Manager. Prior to Compaq, Mike was a systems engineer at Texas Instruments where he developed a real-time operating system, file manager and text editor for a number of portable terminal products. He also led the development of several communication products for the Texas Instruments Professional Computer. Since 2001, Mike has been enjoying retirement and part-time consulting for several high technology companies. Mike has a BSEE degree from the University of New Orleans and is a member of the IEEE. He can be contacted at mikep@pdq.netFaculty Contact: Tom Ioerger (ioerger@cs.tamu.edu)
|
| ||||
| ||||