LABORATORY for ALGORITHMICS and COMBINATORICS
=================================================
Name: Sudebkumar Prasant Pal. Dated: August 26, 2007: 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 five 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. Geometric embeddings of graphs and hypergraphs in multi-dimensional space.
In graph drawing, one essentially studies the limitations in geometric embeddings of relations represented by graphs and hypergraphs. We wish to address issues related to embeddings of Kuratowski's graphs (or similarly defined general graphs and hypergraphs), in multidimensional space. So, we first consider the extreme examples of complete hypergraphs (of n vertices where each hyperedge has exactly r vertices), and derive a few results. We study issues such as (i) the feasibility of embeddings, (ii) simplicial or convex embeddings, and (iii) the number of crossings in simplicial embeddings (when the dimension is not quite high). We wish to further study such issues and also derive bounds on the dimension of space required for crossing-free embeddings. This research is ongoing in collaboration with Saswata Shannigrahi of TIFR Mumbai and Prof. Janos Pach of Courant Institute and CUNY.
=====================================================================================
B. 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 Pruffer-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 Pruffer-like coding and counting labelled hypertrees, presented in the Int. Symp. on Algorithms and Computation (ISAAC), 2006, Kolkata. (Invited for the ISAAC 2006 special issue of the journal "Algorithmica").
======================================================================================
C. 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 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, 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, A. Ghosh, A. Prakash and S. P. Pal, Hypergraph-theoretic characterizations for LOCC incomparable ensembles of multiple multipartite CAT states, to be presented in the Asian Conference on Quantum Information Science, Kyoto, Japan, September 3-6, 2007.
==================================================================================
D. 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 and S. P. Pal, On the communication complexity of certain hypergraph 2-colouring games, manuscript, April 2007, enhanced August 2007.
===================================================================================
E. 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.
[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, 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. Mridul Aanjaneya of 4 th year B Tech CSE (2005-2008) is currently working on certain aspects of visibility with multipple reflections within special classes of polygons.
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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),
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
On multiple-connectedness of
regions visible due to multiple diffuse reflections (click here to
download from http://arXiv.org) ,
Technical Report, TR/IIT/CSE/SPP1,
May 2001, Department of Computer Science and Engineering, IIT Kharagpur,
721302, India, to appear in the proceedings of the
International Conference on Analysis
and Discrete Structures (ICADS 2002), IIT Kharagpur, India, Dec 22-24, 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++.
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||