Aurosish Mishra
In this project, we dealt with a recent application of graph theory - solving Constraint Satisfaction Problems (CSPs) using graph homomorphisms. We analyzed the complexity of digraph H-colorings for different classes of graphs such as chordal graphs, bounded tree-width graphs and bounded degree graphs. Chordal and bounded tree-width graphs were shown to have polynomial time algorithms for H-coloring. For the degree bounded graphs, from (2,2) onwards, the problem becomes NP-Complete. We constructed several clause and variable gadgets to prove this NP-Completeness by reduction from the Satisfiability problems(like 3-SAT and 1-in-3 SAT). While analyzing acyclic bounded degree graphs, we also came up with an interesting open problem regarding the complexity of the (2,2) degree bound case. We also designed a much simpler proof for a celebrated result in graph coloring given by Holyer - the NP-Completeness of 4-bounded 3-colorable graphs. We are planning to submit this paper in a journal for peer review.
Apart from the research, I also got a chance to attend an Industrial Engagement Week and several STEP Workshops as part of the Globalink initiative. Check out a video of me summing up the Canadian experience here.
In this project, we worked on "Wireless Localization" - an interesting variant of the popular Art Gallery Problem. The main objective of this problem is to prevent wireless access to non-paying customers outside a cyber cafe. So, we try to define the inside of a cafe by a monotone Boolean formula using a combination of keys transmitted by routers(guards) placed at certain strategic points. Since, wireless signals transcend boundaries, the problem basically deals with modified concepts of visibility, in which, the edges of the polygon are considered as non-blocking. My focus was to find tighter bounds for the vertex guard setting - guards only at the vertices of the polygon. We analyzed several polygon structures using the notion of polygonal halfplanes. Ultimately, we came up with an improved sub-linear upper bound on the number of vertex guards needed, using the principle of mathematical induction.
In this project, I worked on developing a user-friendly and adaptable "Smart Parking System" in order to alleviate parking hassles in large multi-level parking garages. The design involved placing magnetic sensors in the parking lots that would detect vehicles and communicate with a central base station, which in turn, would update the parking lot guidance system. The guidance system comprising LED displays would account for dynamic entry and exit while directing the vehicles to the nearest parking lot. We handled several design issues such as packet synchronization, multi-hop transmission and packet collision and came up with a working model. I was awarded the prestigious Summer Research Fellowship by the Indian Academy of Sciences in recognition of my work.
In this project, we developed a novel approach for performing quality centric analysis of automative systems. The approach uses two fault analysis methods in tandem: a fault-injection and simulation method to evaluate the quality degradation of output signals of the system, under specific testcases and fault-scenarios; and a look-up table based approach, to obtain the quality degradation of the complete system by a series of table lookups, which store the characterized quality degradation behavior of individual components. The LUT based method performs a quick but approximate analysis and yields better coverage with respect to quality behavior. I focused on improving the characterization of individual components of an automotive system. For this purpose, I used multiple functional testcases to obtain the fault-free golden trajectories. Then, using fault injection technqiues I was able to generate better quality LUTs, which led to proper identification of counter-examples that violate fault-tolerance requirements.
In this project, we want to design a recommendation scheme for suggesting relevant events/products to a mobile user based on his/her interests and activities. The recommendation could be provided based on the user's spatio-temporal location or his/her social group behaviour. For this purpose, we have to perform data-mining on the movement patterns of the user, to create his/her profile, and at the same time, identify various common interest groups a user belongs to. Currently, I am in the process of designing an event-driven simulator to generate realistic movement patterns of the user to test the mining algorithms.
In this project, I designed a Twitter interface based on Bluetooth communication. Each device could follow any number of devices in range. Whenever a user performs a status update, it would be visible on the wall of all his followers. I also computed statistics like updation frequency, inter-contacts duration and transmission latency of my design.
In this project, I studied several NAT traversal protocols such as STUN, TURN and UDP Hole Punching, and implemented a chat client for communication between machines behind NATs(like Skype). Apart from this, I also analyzed the design challenges in building large scale p2p based Video-on-Demand systems regarding the appropriate replication strategy, piece selection techniques, and transmission strategies.
In this project, we analysed the impact of using standard document-analysis techniques to pre-process queries for IR systems. We constructed restricted and unrestricted Word Co-occurrence Networks from the AOL Query Log Corpus and Europarl corpus, and compared the different networks based on their degree distribution, clustering co-efficient and spectral plots.
In this project, we combined the techniques of data shipping and query shipping to design a hybrid query shipping model for optimized performance. We formulated an execution plan for the set of queries, annotating each with the site of its execution (client or server) so as to minimize the time of execution. To achieve this, we built a cost-effective query optimizer based on the Volcano optimizer and obtained improved query response times.