Publications of Gábor Ivanyos

Refereed research papers in journals or conference proceedings

  1. Finding maximal orders in semisimple algebras over Q ,
    with Lajos Rónyai
    Computational Complexity 3 (1993), 245-261.
    MR 95c:11154
  2. Decomposition of algebras over F_q(X_1,...,X_m),
    with Lajos Rónyai and Ágnes Szántó
    Algebra in Engineering, Communication and Computing 5 (1994), 71-90.
    MR 95a:16002
  3. Lattice basis reduction for indefinite forms and an application,
    with Ágnes Szántó
    Discrete Mathemathics 153 (1996), 177-188.
    MR 97c:11071
  4. Computing Cartan subalgebras of Lie algebras,
    with Willem A. de Graaf and Lajos Rónyai
    Applicable Algebra in Engineering, Communication and Computing 7 (1996), 339-349.
    MR 98m:17001
  5. Multiplicative equations over commuting matrices,
    with László Babai , Robert Beals , Jin-Yi Cai , and Eugene M. Luks
    Proc. 7th ACM-SIAM Symp. on Discrete Algorithms (SODA '96), 498-507.
    Preprint: DIMACS Technical Report 95-32.
    MR 1 381 955
  6. Computing Levi decompositions in Lie algebras,
    with Willem A. de Graaf , Alex Küronya , and Lajos Rónyai
    Applicable Algebra in Engineering, Communication and Computing 8 (1997), 291-304.
    MR 99a:17001
  7. Finding the radical of an algebra of linear transformations,
    with Arjeh M. Cohen and David B. Wales
    Journal of Pure and Applied Algebra 117-118 (Proc. MEGA'96) (1997), 177-193.
    MR 98h:16026
  8. Polynomial time algorithms for modules over finite dimensional algebras,
    with Alexander Chistov and Marek Karpinski
    Proc. 1997 Int. Symp. on Symbolic and Algebraic Computation (ISSAC '97), 68-74.
    MR 1809971
  9. Finding the radical of matrix algebras using Fitting decompositions,
    Journal of Pure and Applied Algebra 139 (Proc. MEGA'98) (1999), 159-182.
    MR 1700542
  10. Finding splitting elements and maximal tori in matrix algebras,
    with Willem A. de Graaf,
    In: F. van Oystaeyen, M. Saorin (eds.), Interactions Between Ring Theory and Representations of Algebras, (Proc. Euroconference in Murcia, 1998), Lecture Notes in Pure and Applied Mathematics 210, Marcel Dekker 2000, 95-105.
    MR 1758404
  11. Fast randomized algorithms for the structure of matrix algebras over finite fields,
    Proc. 2000 Int. Symp. on Symbolic and Algebraic Computation (ISSAC 2000), 175-183.
    MR 1805121
  12. Treating the exceptional cases of the MeatAxe,
    with Klaus Lux
    Experimental Mathematics 9 (2000), 373-381 (ps)
    MR 1795309
  13. Deciding finiteness for matrix semigroups over function fields over finite fields,
    Israel Journal of Mathematics 124 (2001), 185-188.
    Preprint: dvi.gz, ps.gz.
    MR 1856512
  14. Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem,
    with Frédéric Magniez and Miklos Santha.
    Proc. 13th SPAA (2001), 263-270.
    Preprint: quant-ph/0102014
    Journal version: International Journal of Foundations of Computer Science 14 No 5 (2003), 723-739.
    MR 2022781
  15. Hidden translation and orbit coset in quantum computing,
    with Katalin Friedl, Frédéric Magniez, Miklos Santha, and Pranab Sen.
    Proc. 35th ACM STOC (2003), 1-9.
    Preprint: quant-ph/0211091 , fresher version (pdf) at Fred.
    MR 2121067
  16. Efficient testing of groups,
    with Katalin Friedl and Miklos Santha.
    Proc. 37th ACM STOC (2005), 157-166.
    Preprint: ps at Miklos.
    MR 2181613
  17. On the black-box complexity of Sperner's Lemma,
    with Katalin Friedl, Miklos Santha, and Yves F. Verhoeven.
    Proc. 15th International Symp. on Fundaments of Computation Theory, Springer LNCS Vol. 3623 / 2005, 245-257.
    Journal version: Theory of Computing Systems 45 (2009), 629-646.
    Preprint: quant-ph/0505185.
    MR 2194850
  18. Quantum computing on lattices using global two-qubit gates,
    with Serge Massar and Attila B. Nagy.
    Physical Review A. Vol. 72, No. 2, 022339 (9 pages).
    Preprint: quant-ph/0502142.
  19. Locally 2-dimensional Sperner problems complete for the polynomial parity argument classes,
    with Katalin Friedl, Miklos Santha, and Yves F. Verhoeven.
    Proc. 6th Italian Conference on Algorithms and Complexity (CIAC 2006), Springer LNCS Vol. 3998 / 2006, 380-391.
    Preprint of the full version: pdf at Yves.
  20. Root filtration spaces from Lie algebras and abstract root groups,
    with Arjeh M. Cohen,
    J. Algebra 300 (2006) 433-454.
    Preprint: pdf at Arjeh.
  21. Root shadow spaces,
    with Arjeh M. Cohen,
    Europ. J. Combin. 28 (2007), 1419-1441.
    Preprint: pdf at Arjeh.
  22. Deciding universality of quantum gates,
    J. Algebra 310 (2007), 49-56.
    Preprint: quant-ph/0603009.
  23. An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups,
    with Luc Sanselme and Miklos Santha,
    Proc STACS'07, Springer LNCS Vol. 4393, 586-597.
    Preprint: quant-ph/0701235.
  24. Constructions for quantum computing with symmetrized gates,
    with Attila B. Nagy and Lajos Rónyai.
    Quantum Information and Computation 8 (2008), 0411-0429.
    Preprint: quant-ph/0608241.
  25. On solving systems of random linear disequations,
    Quantum Information and Computation 8 (2008), 0579-0594.
    Preprint: arXiv:0704.2988 [quant-ph].
  26. An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups,
    with Luc Sanselme and Miklos Santha,
    Proc LATIN'08 (Springer Vol. LNCS 4957), 759-771.
    Journal version: Algoritmica 62 (2012), 480-498.
    Preprint: arXiv:0707.1260 [quant-ph].
  27. Simple Lie algebras having extremal elements,
    with Arjeh M. Cohen and Dan A. Roozemond.
    Indagationes Mathematicae 19 (2008), 177-188.
    Preprint: arXiv:0711.4268 [math.RA].
  28. Schemes for deterministic polynomial factoring,
    with Marek Karpinski and Nitin Saxena.
    Proc. 2009 Int. Symp. on Symbolic and Algebraic Computation (ISSAC '09), 191-198.
    Preprint: arXiv:0804.1974 [cs.CC].
  29. Deterministic polynomial time algorithms for matrix completion problems,
    with Marek Karpinski and Nitin Saxena.
    SIAM Journal on Computing 39:8 (2010), 3736-3751.
    Preprint: arXiv:0907.0774 [cs.CC].
  30. Trading GRH for algebra: algorithms for factoring polynomials and related structures,
    with Marek Karpinski, Lajos Rónyai and Nitin Saxena.
    Matematics of Computation 81 (2012), 493-531
    Preprint: arXiv:0811.3165 [cs.CC].
  31. On the distance between non-isomorphic groups,
    with François Le Gall and Yuichi Yoshida,
    Europ. J. Combin. 33 (2012), 474-476.
    Preprint: arXiv:1107.0133 [math.GR].
  32. Splitting full matrix algebras over algebraic number fields,
    with Lajos Rónyai and Josef Schicho,
    J. Algebra 354 (2012), 211-223.
    Preprint: arXiv:1106.6191 [math.RA].
  33. Finding hidden Borel subgroups of the general linear group,
    Quantum Information and Computation 12 (2012), 0661-0669.
    Preprint: arXiv:1105.4416 [quant-ph].
  34. New bounds on the classical and quantum communication complexity of some graph properties,
    with Hartmut Klauck, Troy Lee, Miklos Santha and Ronald de Wolf,
    Proc. FSTTCS 12 (Leibniz International Proceedings in Informatics Vol. 18), 148-159. (Open access.)

Books, book chapters

  1. Algoritmusok (Algorithms, in Hungarian),
    with Lajos Rónyai and Réka Szabó
    Typotex, Budapest, 1998, 349p.
  2. Computations in associative and Lie algebras ,
    with Lajos Rónyai ,
    a chapter in Arjeh M. Cohen , Hans Cuypers , Hans Sterk (eds), Some tapas of computer algebra ( Algorithms and Computation in Mathematics 4.), Springer-Verlag, Berlin, 1999, 91-120.
    MR 1 679 917/ 1 679 922
    We also wrote a project on quaternion algebras in the same book (pp. 311-314).
  3. Algebra chapter (in Hungarian),
    with Lajos Rónyai
    In: Antal Iványi (ed), Informatikai Algoritmusok vol. II, ELTE Eötvös Kiadó, Budapest, 2005, 838-892. English translation by Csaba Schneider
    In: Antal Iványi (ed), Algorithms of informatics vol. I: Foundations, MondAt Kiadó, Budapest, 2007, 217-274.

Theses

Algorithms for algebras over global fields
Ph. D. Thesis, Hungarian Academy of Sciences, 1996.
dvi.gz, ps.gz.
Classical and quantum algorithms for algebraic problems,
Thesis for the degree doctor of the Hungarian Academy of Sciences, 2007.
thesis (pdf), hungarian summary (pdf).

Drafts, preprints, technical reports

  1. Testing membership in unitriangular matrix groups,
    University at Buffalo Computer Science Technical Report 96-01.
    ps.Z.
  2. Hidden symmetry subgroup problems,
    with Thomas Decker, Miklos Santha and Pawel Wocjan,
    arXiv:1107.2189 [quant-ph].

Unrefereed articles

  1. Algebra and computation at SZTAKI,
    with Lajos Rónyai and András Benczúr.
    ERCIM News 50, (2002) 31-32.
  2. Rejtett részcsoportok és kvantumszámítógépek (Hidden subgroups and quantum computers, in Hungarian)
    Notes (pdf) for a talk given at the Hungarian Academy of Sciences, 2007.

Slides

  1. Quantum algorithms for groups, Groups and Probability, Budapest, 2003.
    with Katalin Friedl
    Part II: dvi.gz, ps.gz
    (Part I at Kati: ps.gz .)
  2. Hidden subgroup minicourse , CWI Amsterdam, 2006.
  3. Tutorial lectures on fast quantum algorithms , De Brún Centre for Computational Algebra, Galway, 2009.
    4. On solving disequations , in Hungarian. MTA SZTAKI 2010.
  4. Shor's discrete log algorithm , in Hungarian. University of Debrecen, 2011.
  5. On the Euclidean algorithm , in Hungarian. Fazekas Highschool, Budapest, 2012.
Last updated December 17, 2012 by Gábor Ivanyos.