Randy Goebel, University of Alberta, Canada | Folk Reducibility and AI-complete Problems
|  Randy is currently President and CEO of ICORE, professor of Computing Science at the University of Alberta, and principle investigator in the Alberta Ingenuity Centre for Machine Learning.
Randy's current interests include applications of machine learning to systems biology, visualization and web mining, as well as work on natural language processing, web semantics, and belief revision. Randy has experience working on industrial research projects in crew scheduling, pipeline scheduling, and steel mill scheduling, as well as scheduling and optimization projects for the energy industry in Alberta.
Randy has held appointments at the University of Waterloo, University of Tokyo, Multimedia University (Malaysia), and has had research collaborations with DFKI (German Centre for AI Research), NICTA (National ICT Australia), RWC (Real World Computing project, Japan), ICOT (Institute for New Generation Computing, Japan), NII (National Informatics Institute, Tokyo), and is actively involved in academic and industrial collaborative research projects in Canada, Australia, Europe, China and Malaysia. | The idea of an "AI-complete" problem has been around since at least the late 1970s, and refers to the more formal idea of the technique used to confirm the computational complexity of NP-complete problems. In the more formal context, the technique of reducibility was used to transform one problem into another that had already been proved to be NP-complete.
Our presentation takes a closer look at what we call "Folk Reducibility," as an approximation to reducibility, in order to try and improve coherence regarding what constitutes tough AI problems. We argue that the traditional AI-complete problems like "the vision problem" and "the natural language problem" are too vague. We provide examples of more precisely specified problems, and argue that relationships amongst them provide a little more insight regarding where and how valuable problem relationships might emerge. | Yuzuru Tanaka, Hokkaido University, Japan | Meme Media and Knowledge Federation |  Yuzuru Tanaka is a professor at the Department of Computer Science, Graduate School of Information Science and Technology, Hokkaido University, and the director of Meme Media Laboratory, Hokkaido University. He is also a professor of National Institute of Informatics. His research areas covered multiprocessor architectures, database schema-design theory, hardware algorithms for searching and sorting, multiport memory architectures, database machine architectures, full text search of document image files, and automatic cut detection in movies and full video search. His current research areas cover meme media architectures, knowledge federation frameworks, and their application to e-Science based on meme media application frameworks such as database and Web visualization frameworks and virtual experiment environment frameworks. He worked as a board member of Japanese Society for Artificial Intelligence (1991-1994), a councilor of Japanese Society for Artificial Intelligence (1995- ), a board member of Information Processing Society of Japan (1995-1996, 1999-2000), an associate member of Japanese Academy of Science (2006- ), and an advisory board member of NTT Research Laboratory (2004- )... He is currently involved in EU’s Integrated Project ACGT (Advancing Clinico-Genomic Trials on Cancer). | With the growing need for interdisciplinary and international availability, distribution and exchange of intellectual resources including information, knowledge, ideas, pieces of work, and tools in reeditable and redistributable organic forms, we need new media technologies that externalize scientific, technological, and/or cultural knowledge fragments in an organic way, and promote their advanced use, international distribution, reuse, and reediting. Although WWW and browsers enabled us to publish and to browse intellectual resources, they do not enable people to reedit and redistribute intellectual resources. We need new media technologies that externalize scientific, technological, and/or cultural knowledge fragments in an organic way, and promote their advanced use, international distribution, reuse, and re-editing. These media can carry a variety of intellectual resources. A media object denotes such a medium with a content intellectual resource. Such media objects can replicate themselves, recombine themselves, and be naturally selected by people reusing them. We call such media 'meme media' since they carry what Richard Dawkins called 'memes'.
The Web works not only as an open publishing repository of documents, but also as an open repository of services represented as Web applications and/or Web services. Pervasive computing denotes an open system of computing resources in which users can dynamically select and interoperate some of these computing resources to perform their jobs satisfying their dynamically changing demands. Such computing resources include not only services on the Web, but also embedded and/or mobile computing resources connected to the Internet through wireless communication. In pervasive computing, the ad hoc definition and/or execution of interoperation among computing resources is called federation. While the integration denotes interoperation among computing resources with standard interoperation interfaces, federation denotes interoperation among computing resources without a priori designed interoperation interfaces. We define knowledge federation as federation of computing resources published in the form of documents.
Federation over the Web is attracting the attention for interdisciplinary and international advanced reuse and interoperation of heterogeneous intellectual resources especially in scientific simulations, digital libraries, and research activities. It may be classified into two types: federation defined by programs and federation by users. Most studies on federation focused on the former type. Their approach is based on both the proposal of a standard communication protocol with a language to use it and a repository with a matching mechanism between service providing programs and service consuming programs. Federation of this type over the Web uses Web service technologies. The second approach tries to federate arbitrarily selected Web applications with each other in an ad hoc manner by extracting arbitrary input forms and output contents from these Web pages, and by defining interoperation among them only through direct manipulation. The latter approach requires knowledge federation technology.
This talk reviews the speaker’s 15 year research on meme media and their application frameworks as well as his 6 year research on their application to knowledge federation of resources over the Web, and then shows some recent applications of these technologies. | Michael Wooldridge, University of Liverpool, UK | Logic for Automated Mechanism Design and Analysis |  Michael Wooldridge is a Professor in the Department of Computer Science at the University of Liverpool, UK. He has been active in multi-agent systems research since 1989, and has published over two hundred articles in the area. His main interests are in the use of formal methods for reasoning about autonomous agents and multi-agent systems. Wooldridge was the recipient of the ACM Autonomous Agents Research Award in 2006. He is co-editor in chief of the journal "Autonomous Agents and Multi-Agent Systems'', and his introductory textbook "An Introduction to Multiagent Systems'' was published by Wiley in 2002. | Recent years have witnessed an explosion of interest in the issues surrounding the use of social choice mechanisms and economic resource allocation mechanisms in settings where the participants are computer programs. Algorithmic mechanism design, and the recent emergence of computational social choice theory are two examples of this growth of interest. If we take seriously the idea that computational agents will participate in economically inspired mechanisms, then it is natural to consider the questions of knowledge representation and reasoning for them. In this talk, we describe our work in this area, particularly as it relates to the specification and verification of social choice mechanisms, and coordination mechanisms such as social laws.
We motivate and introduce the main research issues in the area, discussing, for example, the succinct representation of social choice rules, the complexity of reasoning with such representations, and the handling of preferences. We conclude by showing discussing the relationship of our work to mechanism design as it is understood in economics.
The talk will report joint work with Thomas Agotnes (Bergen), Wiebe van der Hoek (Liverpool), Marc Pauly (Stanford), and Paul E. Dunne (Liverpool). |
|
