Document Open Access Logo

From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces

Authors Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, Xiaoming Sun

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.8.pdf
  • Filesize: 0.75 MB
  • 48 pages

Document Identifiers

Author Details

Xiaohui Bei
  • School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
Shiteng Chen
  • State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
Ji Guan
  • State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
Youming Qiao
  • Centre for Quantum Software and Information, University of Technology Sydney, Australia
Xiaoming Sun
  • Institute of Computing Technology, Chinese Academy of Sciences and University of Chinese Academy of Sciences, Beijing, China

Funding

  • Chen, Shiteng: S. C. was partly supported by the National Key R&D Program of China (Grant No: 2018YFA0306701), and the National Natural Science Foundation of China (Grant No:61702489).
  • Guan, Ji: J. G. was partly supported by the National Key R&D Program of China (Grant No: 2018YFA0306701), the National Natural Science Foundation of China (Grant No: 61832015), and the Key Research Program of Frontier Sciences, CAS, Grant No. QYZDJ-SSW-SYS003.
  • Qiao, Youming: Y. Q. was partly supported by the Australian Research Council DECRA DE150100720.
  • Sun, Xiaoming: X. S. was supported in part by the National Natural Science Foundation of China Grants No. 61832003, 61761136014, the Strategic Priority Research Program of Chinese Academy of Sciences Grant No. XDB28000000, and K. C. Wong Education Foundation.

Acknowledgements

The authors would like to thank Nengkun Yu, James B. Wilson, and Gábor Ivanyos for discussions related to this paper. They would also like to thank George Glauberman and László Pyber for answering their questions on groups, including pointing out the reference [Ol’shanskii, 1978] and clarifying the field characteristic issue in [Buhler et al., 1987].

Cite AsGet BibTex

Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, and Xiaoming Sun. From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 8:1-8:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.8

Abstract

In the 1970’s, Lovász built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings (FCT 1979). A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS 2017). In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory. We first show that the maximum independent set problem and the vertex c-coloring problem reduce to the maximum isotropic space problem and the isotropic c-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exact exponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration. (Dedicated to the memory of Ker-I Ko)

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph coloring
  • Computing methodologies → Algebraic algorithms
  • Computing methodologies → Linear algebra algorithms
Keywords
  • independent set
  • vertex coloring
  • graphs
  • matrix spaces
  • isotropic subspace

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. F. Adams. Vector fields on spheres. Annals of Mathematics, pages 603-632, 1962. Google Scholar
  2. J. F. Adams, Peter D. Lax, and Ralph S. Phillips. On Matrices Whose Real Linear Combinations are Nonsingular. Proceedings of the American Mathematical Society, 16(2):318-322, 1965. Google Scholar
  3. A. A. Albert. Structure of Algebras. Number v. 24 in American Mathematical Society colloquium publications. American Mathematical Society, 1939. URL: https://books.google.com.au/books?id=1G0HcOcoJ1cC.
  4. J. L. Alperin. Large abelian subgroups of p-groups. Transactions of the American Mathematical Society, 117:10-20, 1965. Google Scholar
  5. J. L. Alperin and R. B. Bell. Groups and representations. Number 162 in Graduate texts in mathematics. Springer, 1995. URL: https://books.google.com.au/books?id=q2MPAQAAMAAJ.
  6. VA Antonov. Finite groups with a modular lattice of centralizers. Algebra and Logic, 26(6):403-422, 1987. Google Scholar
  7. J. Gary Augustson and Jack Minker. An analysis of some graph theoretical cluster techniques. Journal of the ACM, 17(4):571-588, 1970. Google Scholar
  8. László Babai. Trading Group Theory for Randomness. In Robert Sedgewick, editor, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pages 421-429. ACM, 1985. URL: https://doi.org/10.1145/22145.22192.
  9. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 684-697, 2016. arXiv:1512.03547, version 2. URL: https://doi.org/10.1145/2897518.2897542.
  10. László Babai, Robert Beals, and Ákos Seress. Polynomial-time theory of matrix groups. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 55-64, 2009. URL: https://doi.org/10.1145/1536414.1536425.
  11. László Babai and Endre Szemerédi. On the Complexity of Matrix Group Problems I. In 25th Annual Symposium on Foundations of Computer Science, West Palm Beach, Florida, USA, 24-26 October 1984, pages 229-240, 1984. URL: https://doi.org/10.1109/SFCS.1984.715919.
  12. Reinhold Baer. Groups with abelian central quotient group. Transactions of the American Mathematical Society, 44(3):357-386, 1938. Google Scholar
  13. Robert Beals. Towards polynomial time algorithms for matrix groups. In Larry Finkelstein and William M. Kantor, editors, Groups and Computation, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, June 7-10, 1995, volume 28 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 31-54. DIMACS/AMS, 1995. URL: https://doi.org/10.1090/dimacs/028/03.
  14. Stuart J. Berkowitz. On Computing the Determinant in Small Parallel Time Using a Small Number of Processors. Inf. Process. Lett., 18(3):147-150, 1984. URL: https://doi.org/10.1016/0020-0190(84)90018-8.
  15. Andreas Björklund and Thore Husfeldt. Exact algorithms for exact satisfiability and number of perfect matchings. Algorithmica, 52(2):226-249, 2008. Google Scholar
  16. Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, and Pekka Parviainen. Fast Zeta Transforms for Lattices with Few Irreducibles. ACM Trans. Algorithms, 12(1):4:1-4:19, 2016. URL: https://doi.org/10.1145/2629429.
  17. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion-exclusion. SIAM Journal on Computing, 39(2):546-563, 2009. Google Scholar
  18. Béla Bollobás. Random Graphs. Number 73 in Cambridge Studies in Advanced Mathematics. Cambridge University Press, second edition, 2001. Google Scholar
  19. Ada Boralevi, Daniele Faenzi, and Emilia Mezzetti. Linear spaces of matrices of constant rank and instanton bundles. Advances in Mathematics, 248:895-920, 2013. Google Scholar
  20. Peter A. Brooksbank, Joshua Maglione, and James B. Wilson. A fast isomorphism test for groups whose Lie algebra has genus 2. Journal of Algebra, 473:545-590, 2017. Google Scholar
  21. Peter A. Brooksbank and James B. Wilson. Computing isometry groups of Hermitian maps. Trans. Amer. Math. Soc., 364:1975-1996, 2012. Google Scholar
  22. Joe Buhler, Ranee Gupta, and Joe Harris. Isotropic subspaces for skewforms and maximal abelian subgroups of p-groups. Journal of Algebra, 108(1):269-279, 1987. Google Scholar
  23. W. Burnside. On some properties of groups whose orders are powers of primes. Proceedings of the London Mathematical Society, 2(1):225-245, 1913. Google Scholar
  24. Jonathan F Buss, Gudmund S Frandsen, and Jeffrey O Shallit. The computational complexity of some problems of linear algebra. Journal of Computer and System Sciences, 58(3):572-596, 1999. Google Scholar
  25. Jesper Makholm Byskov. Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters, 32(6):547-556, 2004. Google Scholar
  26. Jin-yi Cai. Computing Jordan Normal Forms Exactly for Commuting Matrices in Polynomial Time. Int. J. Found. Comput. Sci., 5(3/4):293-302, 1994. URL: https://doi.org/10.1142/S0129054194000165.
  27. John F. Canny. Some Algebraic and Geometric Computations in PSPACE. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 460-467, 1988. URL: https://doi.org/10.1145/62212.62257.
  28. Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Tighter Connections between Derandomization and Circuit Lower Bounds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, pages 645-658, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.645.
  29. Fabrizio Catanese. Moduli and classification of irregular Kaehler manifolds (and algebraic varieties) with Albanese general type fibrations. Inventiones mathematicae, 104(1):263-289, 1991. Google Scholar
  30. Andrea Causin and Gian Pietro Pirola. A note on spaces of symmetric matrices. Linear Algebra and Its Applications, 2(426):533-539, 2007. Google Scholar
  31. Alexander L. Chistov. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic. In Lothar Budach, editor, Fundamentals of Computation Theory, FCT '85, Cottbus, GDR, September 9-13, 1985, volume 199 of Lecture Notes in Computer Science, pages 63-69. Springer, 1985. URL: https://doi.org/10.1007/BFb0028792.
  32. Giuseppe Ilario Cirillo and Francesco Ticozzi. Decompositions of Hilbert spaces, stability analysis and convergence probabilities for discrete-time quantum dynamical semigroups. Journal of Physics A: Mathematical and Theoretical, 48(8):085302, 2015. Google Scholar
  33. Henry Cohn, Robert D. Kleinberg, Balázs Szegedy, and Christopher Umans. Group-theoretic Algorithms for Matrix Multiplication. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 379-388. IEEE Computer Society, 2005. URL: https://doi.org/10.1109/SFCS.2005.39.
  34. P. M. Cohn. The Word Problem for Free Fields: A Correction and an Addendum. J. Symbolic Logic, 40(1):69-74, March 1975. URL: http://projecteuclid.org/euclid.jsl/1183739310.
  35. P. M. Cohn and C. Reutenauer. On the construction of the free field. International Journal of Algebra and Computation, 9(3-4):307-323, 1999. Google Scholar
  36. E. B. Davies. Quantum stochastic processes II. Communications in Mathematical Physics, 19(2):83-105, 1970. Google Scholar
  37. Clément de Seguins Pazzis. Large affine spaces of non-singular matrices. Transactions of the American Mathematical Society, 365(5):2569-2596, 2013. Google Scholar
  38. H. Derksen. Polynomial bounds for rings of invariants. Proceedings of the American Mathematical Society, 129(4):955-964, 2001. Google Scholar
  39. H. Derksen and V. Makam. Polynomial degree bounds for matrix semi-invariants. Advances in Mathematics, 310:44-63, 2017. URL: https://doi.org/10.1016/j.aim.2017.01.018.
  40. Reinhard Diestel. Graph Theory. Number 173 in Springer Graduate Texts in Mathematics. Springer, 5th edition, 2017. Google Scholar
  41. Alexandru Dimca. On the isotropic subspace theorems. Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie, pages 307-324, 2008. Google Scholar
  42. John D. Dixon. Maximal Abelian Subgroups of the Symmetric Groups. Canadian Journal of Mathematics, 23(3):426–438, 1971. URL: https://doi.org/10.4153/CJM-1971-045-7.
  43. Wayne Eberly. Decompositions of Algebras Over R and C. Computational Complexity, 1:211-234, 1991. URL: https://doi.org/10.1007/BF01200061.
  44. David Eppstein. Small maximal independent sets and faster exact graph coloring. J. Graph Algorithms Appl., 7(2):131-140, 2003. Google Scholar
  45. Franco Fagnola and Rely Pellicer. Irreducible and periodic positive maps. Commun. Stoch. Anal, 3(3):407-418, 2009. Google Scholar
  46. Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-NC. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 754-763, 2016. URL: https://doi.org/10.1145/2897518.2897564.
  47. M. Fortin and C. Reutenauer. Commutative/Noncommutative Rank of Linear Matrices and Subspaces of Matrices of Low Rank. Séminaire Lotharingien de Combinatoire, 52:B52f, 2004. Google Scholar
  48. Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson. A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 109-117, 2016. URL: https://doi.org/10.1109/FOCS.2016.95.
  49. Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson. Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 397-409, 2017. URL: https://doi.org/10.1145/3055399.3055458.
  50. I. Gelbukh. Isotropy index for the connected sum and the direct product of manifolds. Publicationes Mathematicae Debrecen, 90(3-4):287-310, 2017. Google Scholar
  51. Daniel Goldstein and Robert M. Guralnick. Alternating forms and self-adjoint operators. Journal of Algebra, 308(1):330-349, 2007. Google Scholar
  52. R. Gow and T. J. Laffey. Pairs of alternating forms and products of two skew-symmetric matrices. Linear algebra and its applications, 63:119-132, 1984. Google Scholar
  53. Ji Guan, Yuan Feng, and Mingsheng Ying. Decomposition of quantum Markov chains and its applications. Journal of Computer and System Sciences, 95:55-68, 2018. Google Scholar
  54. Leonid Gurvits. Classical complexity and quantum entanglement. J. Comput. Syst. Sci., 69(3):448-484, 2004. URL: https://doi.org/10.1016/j.jcss.2004.06.003.
  55. P. Hall. On Representatives of Subsets. Journal of the London Mathematical Society, 1(1):26-30, 1935. Google Scholar
  56. Pavel Hrubeš and Avi Wigderson. Non-Commutative Arithmetic Circuits with Division. Theory of Computing, 11:357-393, 2015. URL: https://doi.org/10.4086/toc.2015.v011a014.
  57. Bo Ilic and J. M. Landsberg. On symmetric degeneracy loci, spaces of symmetric matrices of constant rank and dual varieties. Mathematische Annalen, 314(1):159-174, 1999. Google Scholar
  58. Gábor Ivanyos, Marek Karpinski, Youming Qiao, and Miklos Santha. Generalized Wong sequences and their applications to Edmonds' problems. J. Comput. Syst. Sci., 81(7):1373-1386, 2015. URL: https://doi.org/10.1016/j.jcss.2015.04.006.
  59. Gábor Ivanyos and Youming Qiao. Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing. SIAM Journal on Computing, 48(3):926-963, 2019. URL: https://doi.org/10.1137/18M1165682.
  60. Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam. Non-commutative Edmonds' problem and matrix semi-invariants. Computational Complexity, 26(3):717-763, 2017. URL: https://doi.org/10.1007/s00037-016-0143-x.
  61. Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam. Constructive non-commutative rank computation is in deterministic polynomial time. Computational Complexity, 27(4):561-593, 2018. URL: https://doi.org/10.1007/s00037-018-0165-7.
  62. Gábor Ivanyos and Lajos Rónyai. Computations in associative and Lie algebras. In Some tapas of computer algebra, pages 91-120. Springer, 1999. Google Scholar
  63. Tommy R. Jensen and Bjarne Toft. Graph coloring problems, volume 39 of Wiley-Interscience series in discrete mathematics and optimization. John Wiley & Sons, 1995. Google Scholar
  64. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. On Generating All Maximal Independent Sets. Inf. Process. Lett., 27(3):119-123, 1988. URL: https://doi.org/10.1016/0020-0190(88)90065-8.
  65. Valentine Kabanets and Russell Impagliazzo. Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Computational Complexity, 13(1-2):1-46, 2004. URL: https://doi.org/10.1007/s00037-004-0182-6.
  66. Richard M. Karp, Eli Upfal, and Avi Wigderson. Constructing a perfect matching is in random NC. Combinatorica, 6(1):35-48, 1986. URL: https://doi.org/10.1007/BF02579407.
  67. Emanuel Knill. Protected realizations of quantum information. Physical Review A, 74(4):042301, 2006. Google Scholar
  68. Emanuel Knill and Raymond Laflamme. Theory of quantum error-correcting codes. Physical Review A, 55(2):900, 1997. Google Scholar
  69. Pascal Koiran. Hilbert’s Nullstellensatz Is in the Polynomial Hierarchy. J. Complexity, 12(4):273-286, 1996. URL: https://doi.org/10.1006/jcom.1996.0019.
  70. Kee Yuen Lam and Paul Yiu. Linear spaces of real matrices of constant rank. Linear algebra and its applications, 195:69-79, 1993. Google Scholar
  71. Serge Lang. Algebra. Number 211 in Graduate Texts in Mathematics. Springer-Verlag, New York, third enlarged edition, 2002. Google Scholar
  72. Eugene L. Lawler. A note on the complexity of the chromatic number problem. Inf. Proc. Lett., 5:66-67, 1976. Google Scholar
  73. Eugene L. Lawler, Jan Karel Lenstra, and A. H. G. Rinnooy Kan. Generating all Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms. SIAM J. Comput., 9(3):558-565, 1980. URL: https://doi.org/10.1137/0209042.
  74. David A. Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017. Google Scholar
  75. Mark L. Lewis and James B. Wilson. Isomorphism in expanding families of indistinguishable groups. Groups - Complexity - Cryptology, 4(1):73–110, 2012. Google Scholar
  76. Yinan Li and Youming Qiao. Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 463-474, 2017. arXiv:1708.04501, v2. URL: https://doi.org/10.1109/FOCS.2017.49.
  77. Daniel A Lidar. Review of decoherence free subspaces, noiseless subsystems, and dynamical decoupling. Adv. Chem. Phys., 154:295-354, 2014. Google Scholar
  78. Nathan Linial, Alex Samorodnitsky, and Avi Wigderson. A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Combinatorica, 20(4):545-568, 2000. URL: https://doi.org/10.1007/s004930070007.
  79. László Lovász. On determinants, matchings, and random algorithms. In FCT, pages 565-574, 1979. Google Scholar
  80. László Lovász. An Algorithmic Theory of Numbers, Graphs, and Convexity, volume 50 of CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM, 1986. Google Scholar
  81. László Lovász. Singular spaces of matrices and their application in combinatorics. Boletim da Sociedade Brasileira de Matemática-Bulletin/Brazilian Mathematical Society, 20(1):87-99, 1989. Google Scholar
  82. Roy Meshulam. On k-spaces of real matrices. Linear and multilinear algebra, 26(1-2):39-41, 1990. Google Scholar
  83. Gary L. Miller. On the n log n isomorphism technique (A Preliminary Report). In STOC, pages 51-58, New York, NY, USA, 1978. ACM. URL: https://doi.org/10.1145/800133.804331.
  84. John W. Moon and Leo Moser. On cliques in graphs. Israel Journal of Mathematics, 3(1):23-28, 1965. Google Scholar
  85. Ketan Mulmuley. Geometric Complexity Theory V: Equivalence between Blackbox Derandomization of Polynomial Identity Testing and Derandomization of Noether’s Normalization Lemma. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 629-638, 2012. URL: https://doi.org/10.1109/FOCS.2012.15.
  86. Ketan Mulmuley. Geometric complexity theory V: Efficient algorithms for Noether normalization. Journal of the American Mathematical Society, 30(1):225-309, 2017. Google Scholar
  87. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105-113, 1987. URL: https://doi.org/10.1007/BF02579206.
  88. Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002. Google Scholar
  89. A. Yu Ol’shanskii. The number of generators and orders of abelian subgroups of finite p-groups. Mathematical notes of the Academy of Sciences of the USSR, 23(3):183-185, 1978. Google Scholar
  90. Youming Qiao. Matrix spaces as a linear algebraic analogue of graphs. Under preparation, 2019. Google Scholar
  91. James Renegar. On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part I: Introduction. Preliminaries. The Geometry of Semi-Algebraic Sets. The Decision Problem for the Existential Theory of the Reals. J. Symb. Comput., 13(3):255-300, 1992. URL: https://doi.org/10.1016/S0747-7171(10)80003-3.
  92. Lajos Rónyai. Simple Algebras Are Difficult. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 398-408, 1987. URL: https://doi.org/10.1145/28395.28438.
  93. Lajos Rónyai. Computing the structure of finite algebras. Journal of Symbolic Computation, 9(3):355-373, 1990. Google Scholar
  94. Lajos Rónyai. A Deterministic Method for Computing Splitting Elements in Simple Algebras over Q. J. Algorithms, 16(1):24-32, 1994. URL: https://doi.org/10.1006/jagm.1994.1002.
  95. Tobias Rossmann. Algorithms for Nilpotent Linear Groups. PhD thesis, National University of Ireland, Galway, 2011. Google Scholar
  96. Rudolf Scharlau. Pairs of alternating forms. Mathematische Zeitschrift, 147(1):13-19, 1976. Google Scholar
  97. Jacob T. Schwartz. Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. ACM, 27(4):701-717, 1980. URL: https://doi.org/10.1145/322217.322225.
  98. John Sheekey. On rank problems for subspaces of matrices over finite fields. PhD thesis, University College Dublin, 2011. Google Scholar
  99. Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. The annals of mathematical statistics, 35(2):876-879, 1964. Google Scholar
  100. Ola Svensson and Jakub Tarnawski. The Matching Problem in General Graphs Is in Quasi-NC. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 696-707. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.70.
  101. John Sylvester. On the dimension of spaces of linear transformations satisfying rank conditions. Linear Algebra and its Applications, 78:1-10, 1986. Google Scholar
  102. Francesco Ticozzi and Lorenza Viola. Quantum Markovian subsystems: invariance, attractivity, and control. IEEE Transactions on Automatic Control, 53(9):2048-2063, 2008. Google Scholar
  103. Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. A new algorithm for generating all the maximal independent sets. SIAM Journal on Computing, 6(3):505-517, 1977. Google Scholar
  104. Paul Turán. Egy gráfelméleti szélsőértékfeladatról (On an extremal problem in graph theory). Mat. Fiz. Lapok, 48:436-452, 1941. Google Scholar
  105. William T. Tutte. The factorization of linear graphs. Journal of the London Mathematical Society, 1(2):107-111, 1947. Google Scholar
  106. Leslie G. Valiant. Completeness Classes in Algebra. In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 249-261, 1979. URL: https://doi.org/10.1145/800135.804419.
  107. Christiaan van de Woestijne. Deterministic equation solving over finite fields. In Proceedings of the 2005 international symposium on Symbolic and algebraic computation, pages 348-353. ACM, 2005. Google Scholar
  108. Vincent Vatter. Maximal independent sets and separating covers. The American Mathematical Monthly, 118(5):418-423, 2011. Google Scholar
  109. EP Vdovin. The number of subgroups with trivial unipotent radicals in finite groups of Lie type. Journal of Group Theory, 7(1):99-112, 2004. Google Scholar
  110. R. Westwick. Spaces of matrices of fixed rank. Linear and Multilinear Algebra, 20(2):171-174, 1987. Google Scholar
  111. James B. Wilson. Decomposing p-groups via Jordan algebras. Journal of Algebra, 322(8):2642-2679, 2009. Google Scholar
  112. James B. Wilson. Finding central decompositions of p-groups. Journal of Group Theory, 12(6):813-830, 2009. Google Scholar
  113. James B. Wilson. Optimal algorithms of Gram-Schmidt type. Linear Algebra and its Applications, 438(12):4573-4583, 2013. Google Scholar
  114. Michael M. Wolf. Quantum channels & operations: Guided tour, May 2012. Lecture notes available at URL: https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/MichaelWolf/QChannelLecture.pdf.
  115. David Wood. On the number of maximal independent sets in a graph. Discrete Mathematics and Theoretical Computer Science, 13(3):17, 2011. Google Scholar
  116. Jay A Wood. Spinor groups and algebraic coding theory. Journal of Combinatorial Theory, Series A, 51(2):277-313, 1989. Google Scholar
  117. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Edward W. Ng, editor, Symbolic and Algebraic Computation, EUROSAM '79, An International Symposiumon Symbolic and Algebraic Computation, Marseille, France, June 1979, Proceedings, volume 72 of Lecture Notes in Computer Science, pages 216-226. Springer, 1979. URL: https://doi.org/10.1007/3-540-09519-5_73.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact