Indian Institute of Technology, Kharagpur, India

Department of Computer Science and Engineering

LABORATORY for GEOMETRIC, COMBINATORIAL and ALGEBRAIC COMPUTATION

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

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 the research in this laboratory 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, we have concentrated on certain topics (not restricted to) computational and combinatorial geometry, some aspects of hypergraph theory, and combinatorial aspects of multipartite quantum entanglement.

We are currently pursuing research in the following specific problem areas of fundamental nature. For each of them, we have highlighted below the status so far, the motivation for research, and a very short outline of future research plans.

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

A. Coding and counting graphs, hypergraphs and polyomino tilings.

(i) Optimal Prufer-like coding, and counting labeled hypertrees

We know that labeled 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. User and group ID codes are possible using redundant Prufer-like codes and may find extensive appplications.

(ii) Generalizations for Prufer-like codes and compressing graphs and hypergraphs

We wish to study more possible Prufer-like coding for various structures as well as coding in general for more general cyclic hypergraphs.

Currently, we have also started investigating on limits of possible compression for labeled combinatorial structures in geometric contexts such as tilings. We wish to study the Kolmogorov complexity of polyomino tilings and other combinatorial subdivisions like simplicial complexes in varied appication areas. Mridul Aanjaneya of final year B Tech CSE is working on these problems.

(iii) Feasibility of tiling deficient regions and couting polyomino tilings.

Some work on characterizations of cases admitting domino deficient tromino tilings has already been accepted for publication (see [2]). Some initial work is also reported on counting tromino tilings of rectangles as in [3].

[1] S. Shannigrahi (TIFR Mumbai) 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).

[2] Mridul Aanjaneya (B Tech CSE 2008), Tromino tilings of domino deficient rectangles, to appear in the journal "Discrete Mathematics", Elsevier.

[3] Mridul Aanjaneya (B Tech CSE 2008) and S. P. Pal, Fault-free tromino tilings of rectangles, eprint math.CO/0610925 http://www.arxiv.org

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

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 (RRI Bangalore), 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 (RRI Bangalore), 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, 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 and/or there is more context to be resolved in answering the query. In the specific setting of colouring games for hypergraphs that are not bicolourable, we wish to study correlations and contexts 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 bicolourable, a single colouring strategy does not help in winning the game for each hyperedge-vertex query pair (e,v). 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) and Mridul Aanjaneya of 4th year B. Tech. CSE are currently working on these problems.

[1] R. B. Gokhale (M Tech CSE 2007), Nitin Kumar (M Tech CSE 2008), Mridul Aanjaneya (B Tech CSE 2008) and S. P. Pal, Efficient protocols for hypergraph bicoloring games, manuscript, March 2008.

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

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. New results are reported in [6].

[1] D. Chithra Prasad (Ph. D. 1994-1996), S. P. Pal and Tamal K. Dey. Visibility with multiple diffuse reflections, Computational Geometry:Theory and Applications, Vol. 10, (1998), 187--196.

[2] B. Aronov (Brooklyn Polytechnic, NY), A. Davis, Tamal 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 (Brooklyn Polytechnic,NY), A. Davis, Tamal 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. Chithra Prasad (Ph D 1994-1996), Tamal 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.

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Some earlier research work is enlisted below.

Convex Visibility