=================================================
Name: Sudebkumar Prasant Pal. April 10, 2011 Designation: Professor
Department of Computer Science and Engineering, IIT Kharagpur, 721302, India. (email: spp@cse.iitkgp.ernet.in)
URL: http://www.facweb.iitkgp.ernet.in/~spp/
=====================================================================================
Research summary and proposed plans.
Most of my research revolves around the broad discipline of "Design and Analysis of Algorithms", a fundamental branch of Computer Science and Engineering, dealing with mathematical aspects in the design and performance analysis of computer algorithms. This area of study heavily derives from algebraic and combinatorial techniques due to its very nature, and often applies to problem domains suitably modelled using set systems, relations, graphs and hypergraphs, and geometric objects. In particular, I have concentrated on certain aspects of computational and combinatorial geometry, some aspects of hypergraph theory, and combinatorial aspects of multipartite quantum entanglement.
I am currently pursuing research in the following areas. For each of them, I have highlighted below the status so far, the motivation and a very short outline of future research plans.
=====================================================================================
A. Coding graphs and hypergraphs.
We know that labelled trees of n vertices can be coded in n-2 integers as in Prufer coding. Moreover, such coding (as well as decoding), has been shown to have linear time algorithms. In [1], we show that r-uniform hypertrees on n vertices can also be encoded in what we call Prufer-like codes; the processes of coding/decoding are again linear. Moreover, our method can assign a large number of codes for the same hypertree; we can derive an upper bound on the number of r-uniform hypertrees using our coding technique. We wish to study more possible Prufer-like coding for various structures as well as coding in general for more general cyclic hypergraphs.
[1] S. Shannigrahi and S. P. Pal, Efficient Prufer-like coding and counting labelled hypertrees, presented in the Int. Symp. on Algorithms and Computation (ISAAC), 2006, Kolkata, Lecture Notes in Computer Science, vol. 4288. (Now online: to appear in the journal "Algorithmica", Springer).
======================================================================================
B. Combinatorial aspects of multipartite quantum entanglement.
An ensemble of multiple multipartite quantum entangled (GHZ-like) states shared between a number of geographically distributed nodes represents various combinations of nodes that can exploit entanglement correlations in the distributed problem solving setting, where communication may be restricted to exchange of (classical) information, in contrast to quantum communication. The GHZ-like states may involve any number of parties, starting from bipartite Bell states to m-partite GHZ states. Two such ensembles are called LOCC incomparable if none of them can be derived from the other by means of local operations and classical communication (LOCC). We introduced the notion of representing such ensembles with graphs and hypergraphs and developed certain graph and hypergraph theoretic characterizations for various kinds of incomparable ensembles (see [1,2]). The simple formalism of bicolored merging was developed in [1] to derive such incomparability results.
We are continuing investigations into more such incomparability results, and are also investigating the lattice structure (on the set of possible ensembles) with respect to LOCC comparability (or reducibility) relations. The width of such partial orders is exponential in the number of nodes. These results are derived in [3]. Further, the notion of bicolored merging has been analyzed in terms of (i) partial entropies, and (ii) vertex degrees in (hyper)graphs. Several new incomparability results are derived and some earlier results from [1] are greatly simplified. The extension of such studies in the realm of mixed states and non-maximally entangled states is rather challenging, particularly for multi-partite states. We are also investigating connections between communication complexity and entropy changes in LOCC protocols of various kinds.
Collaborations are continuing with R. Srikanth of Raman Research Institute, Bangalore (currently Faculty Fellow with Poornaprajna Institute of Scientific Research, Bangalore), and Sudhir Kumar Singh of UCLA. Undergraduate students include Anupam Prakash of 4th year B Tech CSE (2004-2008) and Arijit Ghosh of dual degree M Tech CSE (2003-2008).
[1]Sudhir Kumar Singh (M. Sc. Maths and Computing 1999-2004), S. P. Pal, Somesh Kumar and R. Srikanth, A combinatorial approach for studying LOCC transformations of multipartite states, Journal of Mathematical Physics, 46, 122105 (2005).
[2] S. P. Pal, S. Kumar and R. Srikanth, Multipartite entanglement configurations: Combinatorial offshoots into (hyper)graph theory and their ramifications, Quantum Computing: Back Action, IIT Kanpur, March 2006, AIP Conference Proceedings, vol. 864, pp. 156-170.
[3] V. S. Shekhawat (B. Tech. CSE (2007)), A. Ghosh (B. Tech. CSE (2007 Dual Degree)), A. Prakash (B. Tech. CSE (2008)) and S. P. Pal, Hypergraph-theoretic characterizations for LOCC incomparable ensembles of multiple multipartite CAT states, presented in AQIS 2007 (Asian Conference on Quantum Information Science, 2007), Kyoto, Japan, Sept. 03-06, 2007.
==================================================================================
C. Study of correlations in two-party communication problems and their relationships to communication complexity
Correlations between inputs x and y to parties A and B, respectively, can substantially reduce the communication complexity of the problem being solved. One direct way to estimate a (lower) bound is the use of Mehlhorn's rank lower bound, based on the communication matrix. Other techniques use covering the matrix with monotone rectangles.
In [1], we have designed games on complete hypergraphs, winning which requires the two parties to communicate more if there is less correlation in the problem. In the specific setting of colouring games for hypergraphs that are not 2-colourable, we wish to study correlations quantitatively by working out analytic and asymptotic bounds on the number of bits to be communicated so that the game is won for any hyperedge-vertex pair (e,v) where e is given to A and v is given to B. Since the given hypergraphs is not 2-colourable, a single colouring strategy does not work for each (e,v) (query) game. So, multiple strategies are required to be shared by the parties in addition to the (labelled) hypergraph itself. In [1] we have optimal bounds for ordinary complete graphs but an exponential gap for r-uniform complete hypergraphs, r>2, unless we replace a naive deterministic approach by probabilistic arguments. So, we have an example where probabilistic methods help establish optimality where naive deterministic methods apparently fail to do so. Further, using the method conditional probabilities we isolate an actual protocol with the asymptotically optimal communication complexity. We are also defining new games involving similar notions to classify problems by quantifying the amount of correlations in the problems in terms of the umber of strategies required to completely win the query games for all pairs (e,v). Variants and generalizations are being considered. One option is to try randomized protocols as well, with bounded permissible error probabilities. Nitin Kumar of 2nd year M Tech CSE (2006-2008), is working on these problems currently.
[1] R. B. Gokhale, Nitin Kumar, S. P. Pal and Mridul Aanjaneya, Efficient protocols for hypergraph bicoloring games, manuscript, April 2007, enhanced August 2007.
===================================================================================
D. Visibility problems with reflections taken into account.
The study of the combinatorial complexity of regions visible due to multiple reflections is a very interesting and challenging problem in combinatorial and computational geometry. It turns out that the very fundamental topological property like the number of holes in such regions is difficult to estimate. The problem remains open in dimensions above two and also for polygons with holes in two dimensions. Computing these regions is a bigger challenge. This area is yet very nascent but relevant (see [1,2,3]), both theoretically and from the point of view of visibility problems in graphics, etc. Art gallery questions as in [4] and more recent developments as in [5], point to open directions for research.
Mridul Aanjaneya of 4 th year B Tech CSE (2005-2008) is currently working on certain aspects of visibility with multiple reflections within special classes of polygons. Recent results as in [6], were presented as in the 24th European Workshop on Computational Geometry, Nancy, France, March 18-20, 2008.
[1] D. Chithra Prasad (Ph. D. 1994-1996), S. P. Pal and T. K. Dey. Visibility with multiple diffuse reflections, Computational Geometry:Theory and Applications, Vol. 10, (1998), 187--196.
[2] B. Aronov, A. Davis, T. K. Dey, S. P. Pal and D. Chithra Prasad (Ph. D. 1994-1996) Visibility with multiple reflections. Discrete & Computational Geometry, Vol. 20, No. 61, (1998), 61--78. Preliminary version in 5th Scandinavian Workshop on Algorithms Theory, 1996, LNCS 1097, 284-295.
[3] B. Aronov, A. Davis, T. K. Dey, S. P. Pal and D. Chithra Prasad (Ph. D. 1994-1996) Visibility with one reflection. Discrete & Computational Geometry, Vol. 19, No. 4, (1998), 553-574. Preliminary version in 11th ACM Symp. on Computational Geometry, 1995, 316-325.
[4] D. C. Prasad, T. K. Dey and S. P. Pal, Art gallery problems for visibility with reflection, Proceedings of the Fifth National Seminar on Theoretical Computer Science, Bombay, pp. 105-114, August 1995.
[5] S. P. Pal, Siddhartha Brahma (B. Tech. CSE, 2001-2005) and Dilip Sarkar (Univ. of Miami), A linear worst-case lower bound on the number of holes in regions visible due to multiple diffuse reflections, Journal of Geometry, vol 81, no. 1-2, December 2004, Birkhauser-Verlag.
[6] Mridul Aanjaneya, Arijit Bishnu and S. P. Pal, Directly visible pairs and illumination by reflections in orthogonal polygons, Presented in the 24th European Workshop on Computational Geometry, March 18-20, 2008.
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
P. H. D. Ramakrishna (M. Tech. 1998-2000), Sudebkumar
Prasant Pal, Samir Bhalla (M. Tech. 2001-2003), Hironmay Basu (B. Tech. 1999-2003) and Sudhir
Kumar Singh (M. Sc. Maths and Computing, 1999-2004),
Computing sharp and scalable
bounds on errors in approximate zeros of univariate polynomials (click here to
download from http://arXiv.org),
Proceedings of
the International Conference on Analysis and Discrete Structures, December 2003, IIT Kharagpur, India (ICADS 2002).
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
WAN modelling and simulation:
Virtual video caching: A scalable and generic technique for improved quality of video service, S. P. Pal, Rajiv Ranjan Suman, G. S. Anil Kumar and Ruchi Malhotra, Presented in the 2nd Trusted Internet Workshop, HiPC 2003, Hyderabad, India, December 17, 2003 (to appear in the Journal of High Speed Networks, vol. 13, no. 4, 2004, IOS Press).
Analytical modelling of certain kinds of WANs:
Modelling web requests generation:
We have studied the problem of combining temporal locality of web page accesses with overall web page access probablities and designed a linear time, scalable and parallelizable algorithm for generating large synthetic web request streams. The overall distribution like Zipf page popularity distribution is combined with proper stack-distance distribution to account for temporal locality of web page accesses. This work appears in 2003 as a paper entitled `A Scalable, Efficient and General Monte Carlo Scheme for Generating Synthetic Web Request Streams' coauthored with Smruti Sarangi (B. Tech. 1998-2002), P N Sireesh (B. Tech. 1990-2002), in the International Journal of Computer Systems Science and Engineering, CRL Publishing, UK, vol. 18, no. 3, pp. 121-128, May 2003.
We have built two network traffic simulators (NETSIM and SWAN) for performing large-scale high-level network traffic simulations at the application level. The main emphasis is on simulating effects of caching and bandwidth resources on webpage access latency and hit ratios in the caches. We consider multiple origin servers, multiple proxies and several caching nodes in a given network topology, typically coded into a gml file. A visualizer software written in Java helps building the input gml file as well as in viewing the results of the simulation. In NETSIM, request streams at each proxy are generated lazily to save space in long and large simulations. In SWAN, we follow another approach for requests generation. The simulators are written in C++.
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||