Group:Theory Lunch
Title:Instance Compression for NP Problems,Compressive Data Gathering,Deployment Probl
Speaker: Bangsheng Tang, Liwen Xu, Xiaohong Hao University
Time: 2010-12-23 12:00-2010-12-23 13:30
Venue:FIT 1-222


Title: Instance Compression for NP problems

Abstract: The OR-SAT problem is to ask given m CNFs, whether at least one of them is satisfiable. In the work of Fortnow and Santhanam, it is proved that OR-SAT cannot be reduce to any set A where the length is bounded by a polynomial in n, unless PH collapses. This result implies upper bounds for several kernelization problem and size of PCPs for SAT, and also implies that there are no subexponential-size hard sets for NP.This is a follow-up of Harnik and Naor's work, and later followed by Dell and van Melkebeek. If time permits, I will try to explain some possible direction of extension of this work.

Title: Compressive Data Gathering

Abstract: Compressive sensing is a new technique in signal processing that collects a low-dimensional projection of a high-dimensional but sparse signal and recovers the original signal by adopting l1-norm optimization which takes the place of l0-norm optimization that turns out to be NP-hard. I will talk about a new scheme of data gathering in wireless sensor network by using compressive sensing distributedly and show some newly observed properties of matrix that satisfies RIP(Restricted Isometry Property).

Title: Deployment problem in the Wireless Sensor Networks

Abstract: Coverage is critical for wireless sensor networks to monitor a region of interest and provide a good quality of service. Here we have two descriptions of the problem. One is place minimum number of sensors to achieve coverage requirement for a region with obstacles. The problem is NP-hard here. I will introduce a algorithm based on deployment pattern and triangulation in the computational geometry. The other description is: for a given number of sensors, maximized the sensor field coverage.  I will present a Virtual Force algorithm as a sensor deployment strategy to enhance to coverage after an initial random placement of sensors.


Short Bio: