The great Andrew Yao invites and many famous researchers come - what a great event, I'm very glad to have the opportunity to listen to interesting talks at the China Symposium on Theoretical Computer Science.
A brief summary of day 1.
A lot of history and high-level in the morning.
Ronald Graham gave a history of Steiner Trees. His introduction was in Chinese, very impressive, I didn't understand a word though... Next surprise, I didn't know that we don't even know whether Euclidean MST is in NP!
Christos Papadimitriou presented 6 to 8 examples where Computer Science proves its influence to other sciences. A very interesting one was the question whether an optimal system can have an internal conflict (Livnat Pippenger answer this question with yes in 2006), regarding the many internal conflicts in our brain... Then, he made a point that genetic algorithms don't prove useful for combinatorial problems as sexual reproduction favors low risk medium payoff such that we can mate with whoever we want to (Livnat, Papadimitriou 2007).
Avi Wigderson talked about reductions and the history of the PCP theorem.
The afternoon was more concrete.
Sanjeev Arora surveyed SDP and connections to high dimensional geometry. I understood the beginning, became tough towards the end.
Avrim Blum talked about Learning and Clustering. The properties of the similarity measure influence the algorithm to use to get a good clustering. Some problems in clustering are hard but they might be hard because of the model, while the actual problem might be a bit easier.
Maurice Herlihy showed that Renaming is Weaker than Set Agreement (a weaker form of consensus)
And finally, Nir Shavit showed Hashing for Multicore Architectures. It looks like the software will be the bottleneck in the future, hardware switches to Multicore Architectures and software cannot handle the synchronizations. We'll see. Maybe noone will buy the new hardware if the speed-off is too small.
The Recursive Split Ordering reminded me of something I've heard at NII, more to come about that.
2008/10/13
Local Testability and Decodability of Sparse Linear Codes
Long time no post...
Madhu Sudan gave an interesting talk at Tsinghua University.
paper (Kaufman, Sudan)
Some of my notes.
fixed error correcting code, oracle access, check whether correct word resp. not too corrupt, local correction if close to a word, local testing and local correction
example: Hadamard code
code C
linear: x,y \in C => x+y \in C
sparse: t-sparse if C <= n^t (only polynomially many codewords, quite restrictive) large distance: \gamma large distance if for all code words distance at least 1/2-n^-\gamma, as close to 1/2 as possible if these conditions, then k-locally testable (if in addition balanced, k-locally correctible) linear code: dual: all words orthogonal to all code words, dual code also linear => pick a word of dual code, check whether it is orthogonal, that's the check. word should be of low weight (weight k) to allow for a k-local test
corrector to correct coordinate i needs a low-weight word in the dual where coordinate i is 1 and the rest is roughly uniform
=> does dual code have low weight words? roughly uniform even with restriction coordinate i is 1?
weight distribution of primal code: C_i = number of codewords in C with weight i
actually want distribution of dual code C_k^\perp
from primal to dual code weight distributions: MacWilliams identities, hold if we know C_i EXACTLY
C_k^\perp = 1/C \sum C_i P_k(i)
where P_k(i) = \sum (-1)^j (i choose j) (n-i choose k-j) is Krawtchouk Polynomial
the codeword 0 (C_0={0}) contributes most to the sum, polynomial has high value there, low value at all other C_k, as not too many codewords it does not cancel out the highly weighted 0 word
doesn't work for unbalanced because low weight words in dual not guaranteed
and: don't know how to find these words...
Madhu Sudan gave an interesting talk at Tsinghua University.
paper (Kaufman, Sudan)
Some of my notes.
fixed error correcting code, oracle access, check whether correct word resp. not too corrupt, local correction if close to a word, local testing and local correction
example: Hadamard code
code C
linear: x,y \in C => x+y \in C
sparse: t-sparse if C <= n^t (only polynomially many codewords, quite restrictive) large distance: \gamma large distance if for all code words distance at least 1/2-n^-\gamma, as close to 1/2 as possible if these conditions, then k-locally testable (if in addition balanced, k-locally correctible) linear code: dual: all words orthogonal to all code words, dual code also linear => pick a word of dual code, check whether it is orthogonal, that's the check. word should be of low weight (weight k) to allow for a k-local test
corrector to correct coordinate i needs a low-weight word in the dual where coordinate i is 1 and the rest is roughly uniform
=> does dual code have low weight words? roughly uniform even with restriction coordinate i is 1?
weight distribution of primal code: C_i = number of codewords in C with weight i
actually want distribution of dual code C_k^\perp
from primal to dual code weight distributions: MacWilliams identities, hold if we know C_i EXACTLY
C_k^\perp = 1/C \sum C_i P_k(i)
where P_k(i) = \sum (-1)^j (i choose j) (n-i choose k-j) is Krawtchouk Polynomial
the codeword 0 (C_0={0}) contributes most to the sum, polynomial has high value there, low value at all other C_k, as not too many codewords it does not cancel out the highly weighted 0 word
doesn't work for unbalanced because low weight words in dual not guaranteed
and: don't know how to find these words...
2008/04/24
coverage using sensor networks
Long time no post.
Dan Wang, Qlan Zhang, and Jiangchuan Liu give some NP completeness statements for various coverage problems in their paper Self-Protection for Wireless Sensor Networks, which was presented at ICDCS 2006.
Barrier Coverage With Wireless Sensors, a Mobicom 2005 paper by Santosh Kumar, Ten H. Lai, and Anish Arora treats barrier coverage. Paths crossing a region defined by two parallel curves are to be detected by at least k sensors, a possible application could be monitoring the border between two countries. This barrier coverage is weaker than blanket coverage, where all points of a region and not just paths crossing the region have to be covered.
Even though this sounds like a geometric problem suitable for the unit disk model it might not be suitable if k is not 1.
The problem is modeled as a graph: one node for each sensor, edges between sensors if their sensing regions (within the region) overlap, and two additional nodes L (and R) connecting from left (and right) to the geometrically leftmost (rightmost) nodes of the region meaning that following in the direction of the border curve no other node is further left (right) on that very curve. If L and R are k-connected, every crossing path is detected by at least k sensors (therefore this does not work for closed curves).
It is also stated that it cannot be determined locally whether a region satisfies this condition.
Dan Wang, Qlan Zhang, and Jiangchuan Liu give some NP completeness statements for various coverage problems in their paper Self-Protection for Wireless Sensor Networks, which was presented at ICDCS 2006.
Barrier Coverage With Wireless Sensors, a Mobicom 2005 paper by Santosh Kumar, Ten H. Lai, and Anish Arora treats barrier coverage. Paths crossing a region defined by two parallel curves are to be detected by at least k sensors, a possible application could be monitoring the border between two countries. This barrier coverage is weaker than blanket coverage, where all points of a region and not just paths crossing the region have to be covered.
Even though this sounds like a geometric problem suitable for the unit disk model it might not be suitable if k is not 1.
The problem is modeled as a graph: one node for each sensor, edges between sensors if their sensing regions (within the region) overlap, and two additional nodes L (and R) connecting from left (and right) to the geometrically leftmost (rightmost) nodes of the region meaning that following in the direction of the border curve no other node is further left (right) on that very curve. If L and R are k-connected, every crossing path is detected by at least k sensors (therefore this does not work for closed curves).
It is also stated that it cannot be determined locally whether a region satisfies this condition.
2008/02/21
On the Submodularity of Influence in Social Networks (Mossel, Roch; STOC 2007)
Why does viral marketing work? How can one start a blog roll? Who is the most influential agents in a social network? How can we maximize our influence without paying too many bloggers?
Given the social graph (or any other underlying graph structure, e.g., hyperlinks or feed abonnements), applying easy heuristics (high degree nodes, short average distance to the rest of the network) can identify important nodes.
The general threshold model by Kempe, Kleinberg, and Tardos states the following: every node has a flag stating whether it is activated or not; then, a node measures/asks/checks the values of its neighbors, applies its activation function, and then, if the computed value is higher than a certain threshold, it gets activated (and stays so). Threshold values are random, activation functions (from subsets of all nodes to the rational) are monotone increasing (no node has a negative effect) and submodular (the sum of the function values of two sets U, V is at least the sum of the function values of intersection and union, i.e., f(U)+f(V)>=f(U [or] V)+f(U [and] V) drawing a Venn diagram helps to understand that, function value is not increasing too much but increase is diminishing [if we could draw the graph of f, it was not convex and the second derivative f''<=0 - is that right?]).
Of course, even the best viral marketing would need to take into account that thresholds and functions might change with time and that some people might have a negative effect.
The paper deals with the fourth question from above, how to maximize the influence. Say influence works in rounds and starts with a set S of activated nodes. At some point the number of activated nodes does not change any more (in each round at least one node gets activated or the process stops - due to this model). The number of activated nodes sigma(S) depends on the number of initially activated nodes and on their locations (i.e., S). The algorithm (of a viral marketing tool or software) tries to find this initial set of minimal size. It has been shown that even approximation is NP hard (Kempe et al. 2003). However, if sigma was submodular too (the union of sets does not give a blast to your Guerilla marketing campagin), there is hope to find such an approximate set of fixed size.
Mossel and Roch show that sigma is submodular for this process.
Long story. And the proof is still to come.
Submodular means s(A)+s(B)>=s(A [or] B)+s(A [and] B) (variable names got changed, want to prove it for sigma (s for short here)). Coupling is a technique from statistics to analyze random variables, often used to analyze independent random variables coupled to dependent random variables, which are then analyzed instead.
tbctd
Given the social graph (or any other underlying graph structure, e.g., hyperlinks or feed abonnements), applying easy heuristics (high degree nodes, short average distance to the rest of the network) can identify important nodes.
The general threshold model by Kempe, Kleinberg, and Tardos states the following: every node has a flag stating whether it is activated or not; then, a node measures/asks/checks the values of its neighbors, applies its activation function, and then, if the computed value is higher than a certain threshold, it gets activated (and stays so). Threshold values are random, activation functions (from subsets of all nodes to the rational) are monotone increasing (no node has a negative effect) and submodular (the sum of the function values of two sets U, V is at least the sum of the function values of intersection and union, i.e., f(U)+f(V)>=f(U [or] V)+f(U [and] V) drawing a Venn diagram helps to understand that, function value is not increasing too much but increase is diminishing [if we could draw the graph of f, it was not convex and the second derivative f''<=0 - is that right?]).
Of course, even the best viral marketing would need to take into account that thresholds and functions might change with time and that some people might have a negative effect.
The paper deals with the fourth question from above, how to maximize the influence. Say influence works in rounds and starts with a set S of activated nodes. At some point the number of activated nodes does not change any more (in each round at least one node gets activated or the process stops - due to this model). The number of activated nodes sigma(S) depends on the number of initially activated nodes and on their locations (i.e., S). The algorithm (of a viral marketing tool or software) tries to find this initial set of minimal size. It has been shown that even approximation is NP hard (Kempe et al. 2003). However, if sigma was submodular too (the union of sets does not give a blast to your Guerilla marketing campagin), there is hope to find such an approximate set of fixed size.
Mossel and Roch show that sigma is submodular for this process.
Long story. And the proof is still to come.
Submodular means s(A)+s(B)>=s(A [or] B)+s(A [and] B) (variable names got changed, want to prove it for sigma (s for short here)). Coupling is a technique from statistics to analyze random variables, often used to analyze independent random variables coupled to dependent random variables, which are then analyzed instead.
tbctd
@inproceedings{MosselRoch07,
author = {Elchanan Mossel and
S{\'e}bastien Roch},
title = {On the submodularity of influence in social networks},
booktitle = {Proceedings of the 39th Annual ACM Symposium on Theory of
Computing, San Diego, California, USA, June 11-13, 2007},
year = {2007},
pages = {128--134}
}
2008/02/01
Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks (Kalpakis, Dasgupta, Namjoshi; 2003)
The maximum lifetime data gathering with aggregation (MLDA) problem is defined as follows:
The idea is to find such a flow network (a so-called admissible flow network) and then to construct the schedule (a collection of directed aggregation trees, one for each round) from it.
Given a collection of sensors and a base station, together with their locations and the energy of each sensor, find a data gathering schedule with maximum lifetime, where sensors are permitted to aggregate incoming data packets.From a schedule telling when to send which packets we get a flow network with edge capacities being the total number of packets sent through that edge in the schedule. If a schedule has lifetime T (i.e., the network survives for at least T rounds), for each sensor the maximum flow to the base station is at least T as each of the T packets has to eventually reach the base station.
The idea is to find such a flow network (a so-called admissible flow network) and then to construct the schedule (a collection of directed aggregation trees, one for each round) from it.
@article{KDN2003,
author = {Konstantinos Kalpakis and Koustuv Dasgupta and Parag Namjoshi},
title = {Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks},
journal = {Comput. Networks},
volume = {42},
number = {6},
year = {2003},
pages = {697--716},
}
On the Construction of a Maximum-Lifetime Data Gathering Tree in Sensor Networks: NP-Completeness and Approximation Algorithm (Wu, Fahmy, Shroff 2008)
Data aggregation (often called data fusion) is very important in sensor networks in order to gather data from sensors as long as possible.
Wu et al. considers aggregation functions, where (several) packets of size B can be aggregated into one packet of size B, this holds for various functions such as MAX, MIN, AVG, etc. (Mitchell's book describes various models and more complicated data fusion very well)
Therefore, in a (rooted) aggregation tree, any node waits for and receives all values from its children, aggregates it with its own value, and sends the new aggregate to its parent node. Each node sends one packet to its parent and receives one packet from each of its children. If all nodes have the same life-time (a reasonable assumption), the maximum number of children should be minimized (possibly while maintaining a small height of the tree). However, the problem of computing the spanning tree with smallest maximum degree is NP hard. Wu et al. reuses ideas from Furer and Raghavachari (1994)'s algorithm for Steiner trees. (If the Steiner version is considered, only vertices from a distinguished set have to be covered.) Step by step, the algorithm tries to improve the situation for bottleneck nodes (nodes with high degree) without worsening the situation for nodes almost being bottlenecks as follows: iterate through edges and add an edge {u,v} if both u and v are neither bottleneck nor endangered and if within the cycle that appears when adding the edge there is a bottleneck node w, which will then benefit by removing one if its adjacent edges (otherwise, w is said to be blocked by u and v).
This paper is going to be presented at this year's INFOCOM in April (I found it while googling maximum lifetime data aggregation).
Wu et al. considers aggregation functions, where (several) packets of size B can be aggregated into one packet of size B, this holds for various functions such as MAX, MIN, AVG, etc. (Mitchell's book describes various models and more complicated data fusion very well)
Therefore, in a (rooted) aggregation tree, any node waits for and receives all values from its children, aggregates it with its own value, and sends the new aggregate to its parent node. Each node sends one packet to its parent and receives one packet from each of its children. If all nodes have the same life-time (a reasonable assumption), the maximum number of children should be minimized (possibly while maintaining a small height of the tree). However, the problem of computing the spanning tree with smallest maximum degree is NP hard. Wu et al. reuses ideas from Furer and Raghavachari (1994)'s algorithm for Steiner trees. (If the Steiner version is considered, only vertices from a distinguished set have to be covered.) Step by step, the algorithm tries to improve the situation for bottleneck nodes (nodes with high degree) without worsening the situation for nodes almost being bottlenecks as follows: iterate through edges and add an edge {u,v} if both u and v are neither bottleneck nor endangered and if within the cycle that appears when adding the edge there is a bottleneck node w, which will then benefit by removing one if its adjacent edges (otherwise, w is said to be blocked by u and v).
This paper is going to be presented at this year's INFOCOM in April (I found it while googling maximum lifetime data aggregation).
Subscribe to:
Comments (Atom)