|
Research Internship
PCA: Complementation and Model Checking
Mentored by Prof. Paul Gastin & Benedikt Bollig at LSV, ENS Cachan (May - July 2014)
We study the language-theoretical aspects of parameterized communicating automata (PCAs), in which processes communicate via rendez-vous. A PCA, unlike Communicating Automata, is not dependent on topology and can be run on any topology of bounded degree. We show that, under a context bound, which restricts the local behavior of each process, PCAs are effectively complementable and use it to obtain a mondadic second-order (MSO) logic characterization of PCA. As the emptyness problem for context bounded PCAs is decidable for the class of pipelines, rings, and trees, their model-checking problem wrt. MSO properties also becomes decidable.
Stemming the flow of Information in a Social Network
Research Intern at Adobe Research Labs under the supervision of Dr. Balaji Vasan (May - July 2013)
Due to the volatility of social networks, a negative campaign or a rumor can go viral resulting in severe impact to the community. We aim to solve this problem of stemming the flow of a rumor/negative campaign in a network by observing only parts of the network. Given a negative campaign and information about the status of its spread through a few candidate nodes, our algorithm estimates the information flow in the network and based on this estimated flow, finds a set of nodes which would be instrumental in stemming the information flow. The proposed algorithm is tested on real-world networks and its effectiveness is compared against other existing works.
|