Holographic algorithms with unsymmetric signatures

ABSTRACT

Holographic algorithms were introduced by Valiant as a new methodology to derive polynomial time algorithms. Here information and computation are represented by exponential sums using the so-called signatures. These signatures express superpositions of perfect matchings, and are used to achieve exponential sized cancellations, and thereby exponential speedups. Most holographic algorithms so far used symmetric signatures. In this paper we use unsymmetric signatures to give some new holographic algorithms. We also prove a characterization theorem for a class of realizable un-symmetric signatures, each of which may be used to design new holographic algorithms.

REFERENCES

• 1: J-Y. Cai and Vinay Choudhary. Some Results on Matchgates and Holographic Algorithms. In Proceedings of ICALP 2006, Part I. Lecture Notes in Computer Science vol. 4051. pp 703--714. Also available at Electronic Colloquium on Computational Complexity TR06-048, 2006.
• 2: J-Y. Cai and Vinay Choudhary. Valiant's Holant Theorem and Matchgate Tensors. To appear in Theoretical Computer Science. A preliminary version in Proceedings of TAMC 2006: Lecture Notes in Computer Science vol. 3959, pp 248--261.
• 3: Jin-Yi Cai , Vinay Choudhary , Pinyan Lu, On the Theory of Matchgate Computations, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.305-318, June 13-March 16, 2007 [doi>10.1109/CCC.2007.22]
• 4: J-Y. Cai and Pinyan Lu. On Symmetric Signatures in Holographic Algorithms. In the proceedings of STACS 2007, LNCS Vol 4393, pp 429--440. Also available at Electronic Colloquium on Computational Complexity Report TR06-135.
• 5: Jin-Yi Cai , Pinyan Lu, Holographic algorithms: from art to science, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250850]
• 6: Jin-Yi Cai , Pinyan Lu, Bases Collapse in Holographic Algorithms, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.292-304, June 13-March 16, 2007 [doi>10.1109/CCC.2007.6]
• 7: J-Y. Cai and Pinyan Lu. Holographic Algorithms: The Power of Dimensionality Resolved. To appear in ICALP 2007. Also available at Electronic Colloquium on Computational Complexity Report TR07-020.
• 8: W. Foody and A. Hedayat. On theory and applications of BIB designs with repeated blocks, Annals Statist., 5 (1977), pp. 932--945.
• 9: W. Foody and A. Hedayat. Note: Correction to "On Theory and Application of BIB Designs with Repeated Blocks". Annals of Statistics, Vol. 7, No. 4 (Jul., 1979), p. 925.
• 10: C. T. J. Dodson and T. Poston. Tensor Geometry, Graduate Texts in Mathematics 130, Second edition, Springer-Verlag, New York, 1991.
• 11: R. L. Graham, S.-Y. R. Li, and W.-C. W. Li. On the Structure of t-Designs. SIAM. J. on Algebraic and Discrete Methods 1, 8 (1980).
• 12: N. Linial and B. Rothschild. Incidence Matrices of Subsets-A Rank Formula. SIAM. J. on Algebraic and Discrete Methods 2, 333 (1981).
• 13: D. Lichtenstein. Planar formulae and their uses. SIAM J. Comput. 11, 2:329--343.
• 14: M. Jerrum. Two-dimensional monomer-dimer systems are computationally intractable. J. Stat. Phys. 48 (1987) 121--134; erratum, 59 (1990) 1087--1088
• 15: P. W. Kasteleyn. The statistics of dimers on a lattice. Physica, 27: 1209--1225 (1961).
• 16: P. W. Kasteleyn. Graph Theory and Crystal Physics. In Graph Theory and Theoretical Physics, (F. Harary, ed.), Academic Press, London, 43--110 (1967).
• 17: M. Kneser. "Aufgabe 360". Jahresbericht der Deutschen Mathematiker-Vereinigung, 2. Abteilung 58: 27. 1955.
• 18: E. Knill. Fermionic Linear Optics and Matchgates. At http://arxiv.org/abs/quant-ph/0108033
• 19: L. Lovász. "Kneser's conjecture, chromatic number, and homotopy". Journal of Combinatorial Theory, Series A 25: 319--324. 1978.
• 20: Jiří Matoušek, A Combinatorial Proof of Kneser’s Conjecture, Combinatorica, v.24 n.1, p.163-170, January 2004 [doi>10.1007/s00493-004-0011-1]
• 21: K. Murota. Matrices and Matroids for Systems Analysis, Springer, Berlin, 2000.
• 22: H. N. V. Temperley and M. E. Fisher. Dimer problem in statistical mechanics - an exact result. Philosophical Magazine 6: 1061--1063 (1961).
• 23: Leslie G. Valiant, Quantum Circuits That Can Be Simulated Classically in Polynomial Time, SIAM Journal on Computing, v.31 n.4, p.1229-1254, 2002 [doi>10.1137/S0097539700377025]
• 24: Leslie G. Valiant, Expressiveness of matchgates, Theoretical Computer Science, v.289 n.1, p.457-471, 23 October 2002 [doi>10.1016/S0304-3975(01)00325-5]
• 25: Leslie G. Valiant, Holographic Algorithms (Extended Abstract), Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.306-315, October 17-19, 2004 [doi>10.1109/FOCS.2004.34]
• 26: L. G. Valiant. Holographic circuits. In Proc. 32nd International Colloquium on Automata, Languages and Programming, 2005, 1--15.
• 27: L. G. Valiant. Completeness for parity problems. In Proc. 11th International Computing and Combinatorics Conference, 2005, 1--8.
• 28: Leslie G. Valiant, Accidental Algorthims, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.509-517, October 21-24, 2006 [doi>10.1109/FOCS.2006.7]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

General Terms:
Algorithms, Design, Theory