Group:Lunch Meeting
Title: On the Complexity of Trial and Error,Efficient Data Gathering Schemes in Wireles
Speaker: Xiaohui Bei, Liwen Xu University
Time: 2011-11-17 12:00-2011-11-16 14:30
Venue: FIT 1-222

Abstract:

================================
Speaker: Xiaohui Bei
Title: On the Complexity of Trial and Error
================================
Abstract:
Motivated by applications from physics, biochemistry, economics, computer science, etc., where the objects under investigation are unknown or not directly accessible due to various limitations, we propose a trial-and-error model to study search problems with unknown input: Given a search problem with input hidden, we are asked to find a valid solution for the instance. The way for the solution-finding is by proposing candidate solutions, i.e., trials, and using signaled violated constraints, i.e., errors, to prepare the future candidates. The objective is to design time- and/or trial-efficient algorithms to find a valid solution despite the hidden input, or to show that some problems are intrinsically hard when input is unknown.

 

We consider a number of natural problems, and show that the lack of the input knowledge may introduce different levels of extra computational and trial complexities for finding a valid solution. Our complexity results range from polynomial solvable, intractable, to exponential. Our model and results demonstrate the crucial nature of input information for discovering one of its solutions, and reveal a hidden relation between an input and its solutions.

 

=====================================================
Speaker: Xu Liwen
Title: Efficient Data Gathering Schemes in Wireless Sensor Networks
=====================================================

Abstract:
Data gathering is one of the core algorithmic and information theoretic problems in wireless sensor networks. Research in recent years has brought about substantial progress in the field, particularly through the use of highly sophisticated compressive sensing techniques. In this paper, we propose a novel approach that complements these techniques in a fundamental way. The idea is to appropriately sparsify the network, to gather a compressed version of a function (instead of the data itself) with a sparse function base, and to finally recover the original data in the way reminiscent to polynomial approximation and interpolation. We show through theoretical analysis that our scheme significantly outperforms state-of-the-art solutions in terms of efficiency, while matching these solutions in terms of approximation accuracy. For example, in a simple 1D line network, our solution reduces the number of messagetransmissions from the best-known O(kn log n) [Mobicom
09] to O(k2 log2 n), where n is the number of nodes and k is a parameter that depends on the correlation of the underlying sensor data. Finally, we describe a proof of concept implementation on real hardware, and provide simulations showing that our compressed functionbased solution can save up to 80% of communication overhead. Extensive sensitivity analysis shows that our solution is robust, and no more sensitive to errors and parameter changes than existing schemes. an>