LABORATORY for ALGORITHMICS and COMBINATORICS  

=================================================

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.