Talks of the 2007 Edition, July 2nd - 20th
| 06-06-2007 07:00 | Robust development of higher organisms by a chain of self-organizing reactions: Models for pattern formation
Prof. Hans Meinhardt |
|
| Abstract | Development of higher organisms starts with a single cell and leads eventually to a structure of incredible complexity. Nevertheless, development is usually a surprisingly robust process and proceeds often normally even after severe perturbations. Development is under genetic control. However, each cell has essentially the same genetic information. Thus, how can different parts of an embryo differentiate different structures? It will be shown that reliable pattern formation is possible by a chain of self-regulating pattern-forming reactions. We proposed molecular feasible models that describe essential steps. These models are formulated as sets of partial differential equations, describing the synthesis, the spread, the destruction and the interaction of the different substances involved. By computer simulations, it will be shown that the regulatory properties of the predicted interactions correspond closely to the experimental observations. The models found recently strong support by observations on the molecular-genetic level. .../... Animated simulations are available at http://www.eb.tuebingen.mpg.de/meinhardt |
|
|
|
||
| 02-07-2007 14:15 | Predictive Information and Optimal Adaptation
Prof. Naftali Tishby, The Hebrew University of Jerusalem, Israel |
|
| Abstract | The notion of predictive information of a stochastic process was introduced in 2001 as a measure of process complexity and learnability (Bialek, Nemenman, and Tishby 2001). Defined as the mutual information between the past and future of a process, it was shown to asymptotically grow logarithmically with the window size for finite dimensional processes and as a sub-linear power-law when the effective dimension of the process is infinite. A related function - the predictive information curve ? is the maximal number of bits about the future of the process that can be captured by a given number of bits about its past. It can be calculated using the Information Bottleneck method, which also yields approximate minimal sufficient predictors for the process. This function provides the information theoretic bound on the ability of a system, artificial or natural, to adapt to the process. An interesting question is when is that bound achievable a dynamical system. I will discuss the achievability of this bound for the special case of a Gaussian process and a linear dynamical system. This interesting problem links between fundamental concepts of information theory and control theory and may suggest a more general unifying view of information processing by dynamical systems. |
|
|
|
||
| 03-07-2007 10:15 | Human-Centered Robotics
Prof. Oussama Khatib, Stanford University, USA |
|
| Abstract | This discussion focuses on our ongoing effort to develop human-friendly robotic systems that combine the essential characteristics of safety, human-compatibility, and performance. In the area of human-friendly robot design, our effort has focused on new design concepts for the development of intrinsically safe robotic systems that possess the requisite capabilities and performance to interact and work with humans. robotics.stanford.edu/ |
|
|
|
||
| 03-07-2007 10:15 | Back to the Future: Engineering Nanoscale Multicore Microprocessors
Prof. Marios Papaefthymiou, University of Michigan, USA |
|
| Abstract | Process variability raises a host of clocking and timing challenges in the design of GHz-class nanometer-scale microprocessors with multiple cores. Although the magnitude of these challenges is probably unprecedented, their nature is far from new. In fact, in the early years of the clock frequency "arms race" almost two decades ago, these challenges were dealt with using sophisticated level-sensitive clocking schemes with multiple clock phases, as exemplified in the early DEC Alpha microprocessors. With the continuous progress of process scaling, however, these solutions were abandoned in favor of relatively simpler clocking schemes which traded off performance for ease of design and verification. The increasing levels of timing uncertainty introduced by nanometer processes may be calling for a return to the drastic measures of the past. In this talk, I will present our research into the design of GHz-class clock networks for the nano regime. Relying on resonant structures with on-chip inductors, these clock networks yield order-of-magnitude improvements in clock skew and jitter. Furtermore, they enable the use of level-sensitive latches while keeping overall clock power dissipation at lower levels than conventional clocking schemes with edge-triggered flip-flops. In addition to presenting results from our silicon prototyping of resonant-clock datapaths in 0.13um bulk silicon, I will touch on the resonant-clock timing verification problem which, turns out, can be cast as a linear program. I will also give a sneak preview of a 65nm resonant-clocked multicore microprocessor which is currently under development in my research group.
|
|
|
|
||
| 03-07-2007 14:15 | On the critical transmission range in one-dimensional random networks under non-uniform node placement
Prof. Armand Makowski, University of Maryland, USA |
|
| Abstract | We consider N points placed independently on the unit interval [0,1] according to some probability distribution function F. Two nodes communicate with each other if their distance is less than some given transmission range R > 0. We define the critical transmission range R_N as the smallest transmission range such that the N nodes form a connected graph (under the notion of adjacency implied by the ability of nodes to communicate). The distribution of R_N being untractable, we are interested in developing an asymptotic theory for R_N as N becomes large. We carry out the discussion under the assumption that F admits a continuous density f. We identify two qualitatively different cases, namely f_min > 0 and f_min = 0 with f_min the minimum of f over [0,1]. In the process we make contact with the existence and nature of critical thresholds for the property of graph connectivity in the underlying geometric random graph. This is joint work with Ph.D. student Guang Han.
|
|
|
|
||
| 03-07-2007 15:15 | Swarm-bots: Swarms of Self-assembling Robots
Prof. Marco Dorigo, Université Libre de Bruxelles, Belgium |
|
| Abstract | In this talk I will discuss a number of experiments run with the swarm-bot robotic system. A swarm-bot is an artifact composed of a swarm of assembled s-bots. The s-bots are mobile robots capable of connecting to, and disconnecting from, other s-bots. In the swarm-bot form, the s-bots are attached to each other and, when needed, become a single robotic system that can move and change its shape. S-bots have relatively simple sensors and motors and limited computational capabilities. A swarm-bot can solve problems that cannot be solved by s-bots alone. In the talk, I will shortly describe the s-bots hardware and the methodology we followed to develop algorithms for their control. Then I will focus on the capabilities of the swarm-bot robotic system by showing video recordings of some of the many experiments we performed to study coordinated movement, path formation, self-assembly, collective transport, shape formation, and other collective behaviors.
|
|
|
|
||
| 04-07-2007 11:15 | Communication protocols for packet radio networks: algorithmic approach
Prof. Darek Kowalski, University of Liverpool, UK |
|
| Abstract | Packet radio networks model many popular networking environments, e.g., Ethernet, wireless networks, sensor networks. The communication protocols designed for these networks are usually different than ones for the other types of networks, because of a different main communication paradigm. More precisely, a station in a packet radio network cannot successfully receive a message when at least two messages are sent to the station in the same time. This situation is called a collision. The considered communication tasks are: broadcast, gossip, many-to-many and wake-up. We also show that many other tasks can be solved efficiently using the solutions for the abovementioned problems. Among practically used protocols one can list three main groups: random access protocols, channel partitioning protocols and taking-turns protocols. During this lecture we describe the algorithmic backgrounds of these protocols, as well as some other designed algorithms. The complexity of the considered algorithms is analyzed in the specific models. We start with the model of a single-hop radio network, also known as a multiple access channel. Two cases are considered, depending on if a collision detection mechanism is available or not. In the second part of the lecture we extend the algorithms designed for a multiple access channel to multi-hop networks. Prof. Kowalski's homepage http://www.csc.liv.ac.uk/~darek/ |
|
|
|
||
| 04-07-2007 14:15 | Iterative decoding of quantum codes
Prof. Jean-Pierre Tillich, INRIA , France |
|
| Abstract | The idea of using quantum systems for processing information has first been suggested by Feynman and it has developed since into an exciting research area with implications ranging from cryptography to complexity theory. As a concrete example, quantum computers would be able to solve efficiently some hard problems such as integer factorization. A fundamental issue has to be addressed to construct such a computer : it consists in protecting its quantum registers from unwanted evolutions. This can be accomplished by quantum codes. It would be desirable in this context to have quantum analogs of the most powerful families of classical codes, namely LDPC codes and turbo-codes. We will discuss in this talk how such families of codes can be generalized to the quantum setting and what specific issues arise. Prof. Tillich's homepage http://www-rocq.inria.fr/codes/Jean-Pierre.Tillich/ |
|
|
|
||
| 10-07-2007 10:15 | The Gaussian Erasure Channel: Theory and Applications.
Prof. Giuseppe Caire, University of Southern California, USA |
|
| Abstract | We consider a linear time-invariant channel with given transfer function, whose output is corrupted by additive white Gaussian noise and random erasures. Determining the capacity of this channel requires obtaining the asymptotic spectral distribution of a submatrix of a nonnegative definite Toeplitz matrix obtained by retaining each column/row independently and with identical probability. This is a new problem in random matrix theory that does not follow from previously known results. We find explicitly the required asymptotic eigenvalue distribution in terms of a fixed-point equation, that yields the eta-transform of the distribution. This results represents the first known connection between the well-known theory of large Toeplitz matrices (Grenander-Szego) and random matrices. Also, we shall stress an appealing formal analogy with free-probability and the S-transform, even though freeness does not generally apply to this problem. This may suggest that freeness is a too restrictive condition for the S-transform to apply. Furthermore, we find the optimal input spectrum that achieves capacity and show that this is given by the waterfilling solution as in the case of no erasures, but computed for a scaled SNR that takes into account the preence of erasures. We find simple and easily computable upper and lower bounds to capacity, and we characterize the effect of erasures on the key quantities that determine the high-SNR and low-SNR regimes of spectral efficiency versus Eb/N0. Applications of these results are, for example, the capacity of Gaussian channels with impulsive noise, in the limit of very large impulse power, the capacity of a Wyner-model cellular system with centralized processing, where the base stations are connected to the central processor through unreliable links that can be either ``on'' or ``off'' with a certain probability, and the characterization of the mean-square error of a linear predictor (e.g., a Kalman filter) with randomly missing observations. Prof. Caire's homepage http://ee.usc.edu/faculty_staff/faculty_directory/caire.htm |
|
|
|
||
| 10-07-2007 11:15 | Cross-layer Optimization of Wireless Networks
Prof. Stephen Hanly, University of Melbourne, Australia |
|
| Abstract | In this talk, we discuss some recent research we have undertaken on cross-layer optimization of wireless mesh networks. The general framework is that of utility maximization, as proposed by Frank Kelly in his seminal work on TCP flow control. In one problem, we try to maximize user utilities, posing it as a joint problem of flow control, routing, scheduling, and power control. We will describe some tentative progress on this particular problem, and discuss apparent combinatorial difficulties that arise in its solution. This is joint work with Min Cao, Vivek Raganuthan, P.R. Kumar and Vinod Sharma (University of Illinois at Urbana-Champaign). In another problem, we focus on the impact of channel errors on the flow control problem, extend the Kelly framework to include channel errors, and show how a cross-layer approach can result in a much better selection of operating point on the rate-outage tradeoff curve. This is joint work with Qinghai Gao and Junshan Zhang (Arizona State University). Prof Hanly's homepage http://www.ee.unimelb.edu.au/staff/hanly/ |
|
|
|
||
| 10-07-2007 14:15 | Robust development of higher organisms by a chain of self-organizing reactions: Models for pattern formation
Prof. Hans Meinhardt, Max Planck Institute for Developmental Biology, Germany |
|
| Abstract | Development of higher organisms starts with a single cell and leads eventually to a structure of incredible complexity. Nevertheless, development is usually a surprisingly robust process and proceeds often normally even after severe perturbations. Development is under genetic control. However, each cell has essentially the same genetic information. Thus, how can different parts of an embryo differentiate different structures? It will be shown that reliable pattern formation is possible by a chain of self-regulating pattern-forming reactions. We proposed molecular feasible models that describe essential steps. These models are formulated as sets of partial differential equations, describing the synthesis, the spread, the destruction and the interaction of the different substances involved. By computer simulations, it will be shown that the regulatory properties of the predicted interactions correspond closely to the experimental observations. Animated simulations are available at http://www.eb.tuebingen.mpg.de/meinhardt Prof. Meinhardt's homepage http://www.eb.tuebingen.mpg.de/departments/former-departments/h-meinhardt/hans_meinhardt.html |
|
|
|
||
| 10-07-2007 16:15 | Semantic Web: The Story So Far
Prof. Ian Horrocks, University of Manchester, UK |
|
| Abstract | The goal of Semantic Web research is to transform the Web from a linked document repository into a distributed knowledge base and application platform, thus allowing the vast range of available information and services to be more effectively exploited. As a first step in this transformation, languages such as RDF and OWL have been developed; these languages are designed to capture the knowledge that will enable applications to better understand Web accessible resources, and to use them more intelligently. Although realising the Semantic Web still seems some way off, OWL has already been very successful, and has rapidly become a de facto standard for ontology development in fields as diverse as geography, geology, astronomy, agriculture, defence and the life sciences. An important factor in this success has been the availability of sophisticated tools with built in reasoning support. In this talk I will introduce OWL and OWL based tools, and explore the impact that they are having in ontology development and application. I will then go on to discuss some of the shortcomings of OWL, and of the available tool support, that have been identified in such applications, and to present recent work, such as the OWL 1.1 proposal, that addresses these shortcomings. Prof. Horrocks' homepage http://www.cs.man.ac.uk/~horrocks/ |
|
|
|
||
| 11-07-2007 11:15 | Information Theoretic Motivated Protocols for Oblivious Cooperation of Wireless Colocated Transmitters
Prof. Shlomo Shamai, Technion-Israel Institute of Technology |
|
| Abstract | We consider a scenario where a source sends information to a remote destination and where a relay terminal is occasionally present in close proximity to the source, but without the source's awareness. We assume slow fading (block fading) independent channels between the source and the occasional relay to destination, while the channel between the source to the relay is assumed to be additive Gaussian, due to their relatively close proximity. The focus is on oblivious cooperative schemes which make efficient use of the relay when it is present, and still maintain single user optimality when the relay is absent. One such scheme is shown to be Block Markov decode-and-forward which involves correlated transmissions of the source and the relay. The optimal correlation for this scheme is found by solving the optimal outage performance of a 2 X 1 multiple-input single-output (MISO) link under individual power constraints and a correlation constraint. Finally, quantization schemes based on various levels of side information are also discussed. > Joint work with Michael Katz, EE Department, Technion, Haifa 32000, Israel. Prof. Shamai's homepage http://www.ee.technion.ac.il/people/shamai/shamai_hp.html |
|
|
|
||
| 11-07-2007 14:15 | Distributed Algorithms for Optimal Control of Wireless Networks
Professor Edmund Yeh, Yale University, USA |
|
| Abstract | In wireless networks, link capacities are variable quantities determined by transmission powers, channel fading levels, user mobility, as well as the underlying coding and modulation schemes. In view of this, the traditional problems of routing and congestion control must now be jointly optimized with power control and rate allocation at the physical layer. To address this, we consider a multi-commodity flow model for interference-limited wireless networks in which power control and routing variables are chosen to minimize convex link costs reflecting, for instance, average queueing delay. We design a set of node-based distributed gradient projection algorithms which iteratively adjust local control variables with a limited exchange of control messages. We explicitly derive the scaling matrices required in the gradient projection algorithms for fast, guaranteed global convergence, and show how the scaling matrices can be computed in a distributed manner. Furthermore, we show that congestion control can be seamlessly incorporated into our framework. Prof. Yeh's homepage http://www.eng.yale.edu/faculty/vita/yeh.htm |
|
|
|
||
| 12-07-2007 11:15 | Capacity and dependence in communication networks
Prof. Michael Gastpar, Berkeley, EECS, USA |
|
| Abstract | For cooperative networks, capacity hinges on the amount of dependence between the transmitted signals. This was elegantly captured by Shannon for the case of the two-way channel, via inner and outer bounds that only differ in the amount of dependence: The inner bound does not allow for any dependence, and the outer bound allows for full dependence. It is therefore tempting to derive refined and explicit bounds that lie between these two extremes, exploiting the limits imposed by the network topology. This talk will review some old results and recent progress. When all terminals have independent messages, a basic tool to limit dependence is a well-known "cut-set" bound due to Cover and El Gamal. For some topologies involving feedback, we show how to sharpen this bound via an extension of a "dependence-balance" argument due to Hekstra and Willems. This leads to new capacity upper bounds for multiple-access and interference channels with noiseless and noisy feedback. Then, we consider networks with dependent messages where a correlation-based argument due to Witsenhausen can be extended to calculate a limit on dependence. This can be used for example to prove the optimality of uncoded (straight-wire)transmission for a simple sensor network scenario. This is, in part, joint work with Gerhard Kramer.
Prof. Gastpar's homepage http://www.eecs.berkeley.edu/~gastpar/ |
|
|
|
||
| 12-07-2007 16:15 | Network Capabilities: The Good, the Better, and the Future
Prof. Adrian Perrig, Carnegie Mellon University, USA |
|
| Abstract | Network capabilities are a promising approach for building
Denial-of-Service (DoS) resistant networks. In this talk I will survey three generations of capability-based systems: the basic first-generation capability systems providing basic protection against packet flooding, the second-generation systems that provide stronger protection of the request channel, and the third-generation systems that provide advanced receiver-controlled request channel permissions. Prof. Perrig's homepage http://www.ece.cmu.edu/~adrian/ |
|
|
|
||
| 13-07-2007 10:15 | On the Complexity of Register Coalescing
Dr Fabrice Rastello, Ecole Normale Supérieure de Lyon, France |
|
| Abstract | Memory transfers are becoming more important to optimize, for both performance and power consumption. With this goal in mind, new register allocation schemes are developed, which revisit not only the spilling problem but also the coalescing problem. Indeed, a more aggressive strategy to avoid load and store instructions may increase the constraints to suppress move instructions, i.e., the coalescing phase. This talk is devoted to the complexity of this phase, in particular in the light of recent developments on the SSA form. We distinguish several optimizations that occur in most coalescing heuristics: a) aggressive coalescing removes as many moves as possible, regardless of the colorability of the resulting interference graph; b) conservative coalescing removes as many moves as possible while keeping the colorability of the graph; c) incremental conservative coalescing removes one particular move while keeping the colorability of the graph; d) optimistic coalescing coalesces moves aggressively, then gives up about as few moves as possible so that the graph becomes colorable. We almost completely classify the NP-completeness of these problems, discussing also on the structure of the interference graph: arbitrary, chordal, or k-colorable in a greedy fashion. We believe that such a study is a necessary step for designing new coalescing strategies. Dr Rastello's homepage http://perso.ens-lyon.fr/fabrice.rastello/ |
|
|
|
||
| 16-07-2007 11:15 | Vision-based Handy User Interaction Interfaces
Prof. Yuanchun Shi, Tsinghua National Lab of Information Science and Technology, China |
|
| Abstract | As more and more multimedia information displays flood our living world, we are wanting convenient means to interact with the displayed content. Cameras embedded in projectors, or walls, or display corners, or mobile phones can capture the hand pointing, sketching, moving and transform the hand action into direct manipulation to displayed content. In my lab at Tsinghua University, several handy user interaction interfaces are developed based on computer vision. uPen is a pen-like laser pointer combined with a contact pushed switch and three press buttons, which allows users to interact by pointing or writing on large displays at a distance or directly on the surface with full function of mouse. CamTracker tracks user?s finger touch input on display surface based on binocular vision which can augment ordinary display into a touch sensitive one. uTable with uPens is table-top collaborative interactive display for multiple users and the table itself still has the functions of usual table, moreover, multiple uTables can be seamlessly connected to larger table. DirectPointer and CamPointer in user?s hand can control the cursor on the display by analyzing the view of the camera. And CamPointer can freely control 3D models. They can be implemented into handheld devices like mobile phone or PDA. Prof. Shi's homepage http://media.cs.tsinghua.edu.cn/en/shiyc |
|
|
|
||
| 16-07-2007 14:15 | Symmetric-key private authentication: techniques and metrics
Prof. Levente Buttyan, Budapest University of Technology and Economics, Hungary |
|
| Abstract | Prof. Buttyan's homepage Prof. Buttyan's homepage http://www.hit.bme.hu/~buttyan/ |
|
|
|
||
| 17-07-2007 10:15 | User Experience and System Issues
Professor Joseph A. Konstan, University of Minnesota, USA |
|
| Abstract | Over the past decade, recommender systems employing collaborative filtering technology have evolved from research proofs-of-concept to commonplace components of e-commerce web sites and direct marketing. At the same time, research has moved forward to embrace more sophisticated algorithms and more detailed exploration of the user experience. This talk introduces recommender systems and the algorithms and interfaces used to construct them. It then reviews recent highlights from the 13-year-old GroupLens Research Project, including advances in algorithms, innovations in user interfaces for enhancing user experience, experiments in applying recommender systems to digital libraries, and developments in leveraging the power of on-line communities to construct and maintain artifacts of lasting value.
Prof. Konstan's homepage http://www-users.cs.umn.edu/~konstan/ |
|
|
|
||
| 17-07-2007 11:15 | The design of safe automotive electronic systems: some problems, solutions and open issues
Prof. Françoise Simonot, Ecole des Mines de Nancy, France |
|
| Abstract | From the last decade, the number of software based systems embedded in a car increases every year. The reasons for this evolution are economical as well as technological. On the one hand, this situation is the result of the decreasing cost of hardware components, their increasing reliability and performances and the emergence of embedded fieldbuses; on the other hand, software technology makes easier and less costly the introduction of new functions. Formerly confined to functionalities such as engine or chassis control, this evolution now affects all car domains: wipers, door controls, lights, air condition, braking assistance, multimedia, etc. In the future, even critical functions, as for example, braking or steering, will be fully controlled by electronic systems leading to the X-by-Wire concept. The realization of such systems is obtained through a complex cooperative development process shared by several actors, in particular, OEM (carmakers) and tier-1 suppliers. Furthermore, it's no longer possible to study each system as a stand-alone one and all the partners involved in the design of these systems have to observe a global and common view of the whole embedded architecture. In this context, the main challenge is nowadays to provide means for an efficient development of a safe and optimal embedded system. In this presentation, we will focus on some keywords whose impact and meaning may look antagonist. For example, component, modularity and reusability are recurrent concepts aiming to increase the efficiency of a development while reducing its length. Nevertheless, these principles can be opposed to safety, reliability, dependability purposes. Indeed, the verification of these required properties have to be done on the whole system and not only on a single component. Therefore, we have to complete these first concepts and to introduce the notion of composition of components and moreover of interoperability of components. We will show how this composition can be described through a reference model of embedded architecture that provides on the one hand a standard embedded middleware and on the other hand, an architecture description language. Then, we will focus on the verification of safety/dependability properties and identify which kind of activities they can require and how these activities are related to the first point. Prof. Simonot's homepage http://www.loria.fr/~simonot/ |
|
|
|
||
| 17-07-2007 14:15 | Video-based modelling and animation of people
Prof. Adrian Hilton, University of Surrey, UK |
|
| Abstract | Capture and representation of a persons appearance during movement in a form that can be manipulated for highly realistic computer animation in games and film is an open research problem. This talk will present a number of approaches that have been introduced to capture people from multiple view video using both model-based and model-free computer vision methodologies. Surface Motion Capture (SurfCap) will be introduced which allows representation and animation control of people with the captured dynamics of clothing during movement. SurfCap will be presented as an analogous technology to skeletal human motion capture using markers (MoCap) which has become a standard production tool. Surface motion graphs are used to animate people from multiple captured surface sequences allowing control of movement and action. Surface matching methods based on geometry image sequences using spherical parameterisation are used to transition between captured motion sequences and reconstruct skeletal movement. SurfCap's potential as a future technology for production in games and film will be discussed. Prof. Hilton's homepage http://www.ee.surrey.ac.uk/Personal/A.Hilton/ |
|
|
|
||
| 17-07-2007 15:15 | Interference Channels with generalized feedback
Prof. Daniela Tuninetti, University of Illinois, USA |
|
| Abstract | Prof. Tuninetti's homepage Prof. Tuninetti's homepage http://www.ece.uic.edu/~daniela/ |
|
|
|
||
| 18-07-2007 10:15 | Increasing the Resilience of Routing in Untrusted and Collapsing Networks
Prof. Dan Rubenstein, Columbia University, USA |
|
| Abstract | Distributed routing protocols were designed to be robust to periodic failures, but generally assume that all nodes can be trusted to correctly implement the protocol, and that nodes will not fail too quickly. Unfortunately, history has demonstrated that sometimes inaccurate information can be propagated with devastating consequences. And networks of the future that are to be quickly deployed in hazardous environments can at times expect nodes to fail suddenly or rapidly. In this talk, we first describe a theoretical framework we have developed that allows us to understand when, using state information provided by a distributed routing protocol, this information can be used to detect erroneous propagation of information. We derive a polynomial-time algorithm for distance vector (Bellman-Ford) and Path-Vector (BGP) style protocols called Strong Detection and prove that if our algorithm cannot detect an error, then the error is undetectable, given the existing state information. Next, we look at a resilient routing technique that utilizes a coding technique whose structure varies with time to increase the fraction of generated data that can be extracted from the network over time as nodes that store and forward data fail. Prof. Rubenstein's homepage http://www1.cs.columbia.edu/~danr/ |
|
|
|
||
| 18-07-2007 11:15 | Error Detection of Linear Block Codes
Prof. Marc Fossorier, University of Hawaii |
|
| Abstract | Prof. Fossorier's homepage Prof. Fossorier's homepage http://www-ee.eng.hawaii.edu/faculty/detail.php?usr=13 |
|
|
|
||
| 18-07-2007 14:15 | Anonymous Mobility in Suspicious MANETs
Prof. Gene Tsudik, University of California, Irvine, USA |
|
| Abstract | In many traditional mobile network scenarios, nodes establish communication on the basis of (public) identities. However, in some hostile and suspicious MANET settings, node identities must not be exposed and node movements must not be traceable. Instead, nodes need to communicate on the basis of their current locations. In this work, we address some interesting issues arising in such MANETs by designing an anonymous routing framework (ALARM). It uses nodes' current locations to construct a secure MANET "map". Based on the current map, each node can decide which other nodes it wants to communicate with. ALARM takes advantage of some advanced cryptographic primitives to achieve node authentication, data integrity, anonymity and untraceability (tracking-resistance). It also offers resistance to insider (including Sybil) attacks.
Prof. Tsudik's homepage http://www.ics.uci.edu/%7Egts/ind1.html |
|
|
|
||
| 18-07-2007 16:15 | Coordinated Multi-Robot Exploration
Prof. Wolfram Burgard, Albert-Ludwigs-Universität Freiburg, Germany |
|
| Abstract | In this presentation we consider the problem of exploring an unknown environment by a team of robots. As in single-robot exploration the goal is to minimize the overall exploration time. The key problem to be solved therefore is to choose appropriate target points for the individual robots so that they simultaneously explore different regions of their environment. We present an approach for the coordination of multiple robots which simultaneously takes into account the costs of reaching a target point and the utility of target points. The utility of target points is given by the size of the unexplored area that a robot can cover with its sensors upon reaching a target position. Whenever a target point is assigned to a specific robot, the utility of the unexplored area visible from this target position is reduced for the other robots. This way, a team of multiple robots assigns different target points to the individual robots. The technique has been implemented and tested extensively in real-world experiments and simulation runs. We will present experimental results which demonstrate that our coordination technique significantly reduces the exploration time compared to previous approaches. We also will describe different extensions of this approach towards limited communication and limited bandwidth of the communication channel. Additionally, we will describe how to utilize high-level information about the type of places to improve the exploration process. Prof. Burgard's homepage http://www.informatik.uni-freiburg.de/~burgard/ |
|
|
|
||
| 19-07-2007 10:15 | Multi-Robot Teams: Separating Teamwork and Taskwork
Prof. Gal A. Kaminka, Bar Ilan University, Israel |
|
| Abstract | Teams of multiple robots are of much interest in real-world and research domains, ranging from simulated pilots in commercial applications, through coordinated spaceships, to teams of unmanned vehicles moving in formation or covering an area together. From an agents perspective, challenges in building such teams are many; some related to a particular task (taskwork), and some more general in question (teamwork). In this talk, I will present my group's research into task-specific and task-general methods in multi-robot teams, building and mixing together ideas from AI architectures, multi-agent systems theory, and graph algorithms. The research emphasizes empirical and analytical investigations of robotic teams in a variety of tasks, robot morphologies, and interaction conditions. In this talk, highlights include: (i) Robust multi-robot coverage algorithms, using spanning-trees and Hamiltonian cycles; (ii) Formation-maintenance algorithms which utilize graph algorithm to manage sensor utilization; and (iii) BITE, a situated control architecture, guided by ideas from teamwork theory.
Prof. Kaminka's homepage http://www.cs.biu.ac.il/~galk/ |
|
|
|
||
| 19-07-2007 11:15 | The Information Lost in Erasures
Prof. Sergio Verdu, Princeton University, USA |
|
| Abstract | We consider sources and channels with memory observed through erasure channels. In particular, we examine the impact of sporadic erasures on the fundamental limits of lossless data compression, lossy data compression, channel coding, and denoising. We define the erasure entropy of a collection of random variables as the sum of entropies of the individual variables conditioned on all the rest. The erasure entropy measures the information content carried by each symbol knowing its context. The erasure entropy rate is shown to be the minimal amount of bits per erasure required to recover the lost information in the limit of small erasure probability. When we allow recovery of the erased symbols within a prescribed degree of distortion, the fundamental tradeoff is described by the erasure rate-distortion function which we characterize. We show that in the regime of sporadic erasures, knowledge at the encoder of the erasure locations does not lower the rate required to achieve a given distortion. When no additional encoded information is available, the erased information is reconstructed solely on the basis of its context by a denoiser. Connections between erasure entropy and discrete denoising are developed. The decrease of the capacity of channels with memory due to sporadic erasures is also characterized in wide generality. (Joint work with T. Weissman) Prof. Verdu's homepage http://www.princeton.edu/~verdu/ |
|
|
|
||
| 19-07-2007 14:15 | Structural Invariants
Prof. Rupak Majumdar, University of California, Los Angeles |
|
| Abstract | We present structural invariants (SI), a new technique for incrementally overapproximating the verification condition of a program in static single assignment form by making a linear pass over the dominator tree of the program. The 1-level SI at a program location is the conjunction of all dominating program statements viewed as constraints. For any k, we define a k-level SI by recursively strengthening the dominating join points of the 1-level SI with the (k-1)-level SI of the predecessors of the join point, thereby providing a tunable selector to add path-sensitivity incrementally. By ignoring program paths, the size of the SI and correspondingly the time to discharge the validity query remains small, allowing the technique to scale to large programs. We have found experimentally that even with k less than equal to 2, for a set of open-source programs totaling 570K lines and properties for which specialized analyses have been previously devised, our method provides an automatic and scalable algorithm with a low false positive rate. We provide an additional application of structural invariants to checking and inferring disjoint union types in C programs. [Joint work with Ranjit Jhala and Ru-Gang Xu] Prof. Majumdar's homepage http://www.cs.ucla.edu/~rupak/ |
|
|
|
||
| 19-07-2007 15:15 | Random Constraint Satisfaction Problems: Algorithms from Physics
Prof. Dimitris Achlioptas, University of California in Santa Cruz, USA |
|
| Abstract | For a number of random constraint satisfaction problems, such as random k-SAT and random graph coloring, we now have excellent estimates of the largest constraints-to-variables ratio for which they have solutions. These estimates imply that all known polynomial- time algorithms stop finding solutions much before solutions cease to exist. To understand the origin of this phenomenon we study the evolution of the structure of the space of solutions in random CSPs as constraints are added. In particular, we will survey both what physicists hypothesize happens in this evolution, and what has been rigorously proven so far. We will see that the rigorous results are both in agreement with the physics predictions and help demystify Survey Propagation, an extremely successful heuristic proposed by physicists for random CSPs.
Prof. Achlioptas' homepage http://www.cs.ucsc.edu/~optas/ |
|
|
|
||
| 20-07-2007 10:15 | Two-photon Interference in Quantum Imaging and Communication Systems
Dr Neil Gunther, Performance Dynamics Company, CA, USA |
|
| Abstract | The photon is the carrier of information (qubit) in optical communication systems. Being a purely quantum phenomenon, the photon needs to be represented using the correct quantum design-rules to ensure the proper operation of VLSI-scale devices for communications, cryptography, and imaging. Such quantum design-rules were presented at SRI 2006 using the Feynman quantum path-integral (QPI) representation of the photon. Those quantum design-rules covered single-photon interference effects. VLSI single-photon detectors (SPADs) have been developed by Prof. Edoardo Charbon and his group. In this lecture, I will report on our investigations into 2-photon interference effects. In particular, I will discuss the similarities and differences between interference due to 2-photon "bunching" and biphoton entanglement.
Dr Gunther's homepage http://www.perfdynamics.com/Bio/njg.html |
|
|
|
||
| 20-07-2007 15:15 | Ultrasonic airborne transducer arrays: technology and applications
Prof. Lorenzo Capineri, University of Florence, Italy |
|
| Abstract | Ultrasonic transducers are now widely used to devise instruments useful for medical, industrial and research applications, since the first piezoelectric transducer developed by Langevin as submarine detector in 1917. He considered also the electrostatic actuation for the submarine detector. Nowadays both piezoelectric and electrostatic transducers are still subject of research for the fabrication of arrays integrated with electronics. For airborne applications new materials and fabrication technologies are presented. Examples of ultrasonic transducer arrays system developed by our research group for objects detection in two and three dimensional space are shown. Prof. Capineri's homepage http://www.echommunity.com/EchommunityPortal/uscnd/biography.htm |
|
|
|
||