Publications of Gábor Ivanyos

Refereed research papers in journals or conference proceedings

  1. Explicit equivalence of quadratic forms over Fq(t),
    with     Péter Kutas and Lajos Rónyai,
    Finite Fields and Their Applications 55 (2019), 33-63.
    Preprint: arXiv:1610.08671 [math.RA].
  2. On learning linear functions from subset and its applications in quantum computing,
    with     Miklos Santha and Anupam Prakash .
    Proc. ESA 2018, LIPIcs Vol. 112, Art No. 66.
    Preprint: arXiv:1806.09660 [quant-ph].
  3. Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing,
    with     Youming Qiao
    Proc. SODA 2018, 2357-2376.
    Journal version: SIAM J. Comput. 48 (2019), 926-963.
    Preprint: arXiv:1708.03495 [cs.DS].
  4. Constructive non-commutative rank computation is in deterministic polynomial time,
    with     Youming Qiao and K. V. Subrahmanyam
    Proc. ITCS 2017 (LIPIcs Vol. 67) (2017), Art. No. 55
    Journal version: Computational Complexity 27 (2018), 561-593.
    Preprint: arXiv:1512.03531 [cs.DS].
  5. Non-commutative Edmonds' problem and matrix semi-invariants,
    with     Youming Qiao and K. V. Subrahmanyam
    Computational Complexity 26 (2017) 717-763.
    Preprint: arXiv:1508.00690 [cs.DS].
  6. Computing explicit isomorphisms with full matrix algebras over Fq(x),
    with     Péter Kutas and Lajos Rónyai,
    Foundations of Computational Mathematics 18 (2018), 381-397.
    Preprint: arXiv:1508.07755 [math.RA].
  7. Polynomial interpolation and identity testing from high powers over finite fields,
    with     Marek Karpinski, Miklos Santha, Nitin Saxena and Igor E. Shparlinski.
    Algorithmica 80 (2018), 560-575.
    Preprint: arXiv:1502.06631 [cs.DS].
  8. On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz
    with     Alexander Belov, Youming Qiao, Miklos Santha and Siyi Yang.
    Proc. CCC 2017, (LIPIcs Vol. 79) (2017) Art. No. 30.
    Preprint: arXiv:1710.08602 [cs.CC].
  9. Irreducibility and r-th root finding over finite fields,
    with     Vishwas Bhargava, Rajat Mittal and Nitin Saxena.
    Proc. ISSAC 2017, 37-44.
    Preprint: arXiv:1702.00558 [cs.CC].
  10. Solving systems of diagonal polynomial equations over finite fields,
    with     Miklos Santha
    Proc. FAW 2015, Springer LNCS, Vol. 9130 (2015), 125-137.
    Journal version: Theoretical Computer Science 657 (2017) 73-85.
    Preprint: arXiv:1503.09016 [cs.CC].
  11. Quantum computation of discrete logarithms in semigroups,
    with     Andrew M. Childs
    J. Math. Cryptology 8 (2014), 405-416.
    Preprint: arXiv:1310.6238 [quant-ph].
  12. An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group,
    with     Thomas Decker, Raghav Kulkarni, Youming Qiao and Miklos Santha
    Proc. MFCS 2014, Springer LNCS Vol. 8635, 226-238.
    Journal version: Theoretical Computer Science, to appear.
    Preprint: arXiv:1406.6511 [quant-ph].
  13. On the complexity of trial and error for constraint satisfaction problems
    with     Raghav Kulkarni, Youming Qiao, Miklos Santha and Aarthi Sundaram,
    Proc. ICALP 2014, Springer LNCS Vol. 8572, 663-675.
    Journal version: Journal of Computer and System Sciences, 92 (2018), 48-64 .
    Preprint: arXiv:1406.5336 [cs.CC].
  14. Polynomial time quantum algorithms for certain bivariate hidden polynomial problems,
    with     Thomas Decker, Peter Høyer and Miklos Santha
    Quantum Information and Computation 14 (2014), 790-806.
    Preprint: arXiv:1305.1543 [quant-ph].
  15. Deterministic polynomial factoring and association schemes,
    with     Manuel Arora, Marek Karpinski and Nitin Saxena.
    LMS J. of Computation and Mathematics 17 (2014), 123-140.
    Preprint: arXiv:1205.5653 [cs.CC].
  16. Generalized Wong sequences and their applications to Edmonds' problems,
    with     Marek Karpinski, Youming Qiao and Miklos Santha
    Proc. STACS'14 (Leibniz International Proceedings in Informatics Vol. 25), 397-408. (Open access.)
    Journal version: J. Comput. Syst. Sci. 81 (2015), 1373-1386.
    Preprint: arXiv:1307.6429 [cs.CC].
  17. Hidden translation and translating coset in quantum computing,
    with Katalin Friedl, Frédéric Magniez, Miklos Santha, and Pranab Sen.
    SIAM Journal on Computing 43:1 (2014), 1-24.
    Preliminary version: Hidden translation and orbit coset in quantum computing,
    Proc. 35th ACM STOC (2003), 1-9.
    Preprint: quant-ph/0211091.
    Authors' copy from the publisher: pdf.
  18. Hidden symmetry subgroup problems,
    with Thomas Decker, Miklos Santha and Pawel Wocjan,
    SIAM Journal on Computing 42:5 (2013), 1987-2007.
    Preprint: arXiv:1107.2189 [quant-ph].
    Authors' copy from the publisher: pdf.
  19. Improved algorithms for splitting full matrix algebras,
    with Ádám D. Lelkes and Lajos Rónyai,
    JP Journal of Algebra, Number Theory and Applications 28 (2013), 141-156.
    Preprint: arXiv:1211.1356 [math.RA].
  20. 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.)
  21. 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].
  22. Finding hidden Borel subgroups of the general linear group,
    Quantum Information and Computation 12 (2012), 0661-0669.
    Preprint: arXiv:1105.4416 [quant-ph].
  23. 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].
  24. 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].
  25. 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].
  26. 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].
  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. 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].
  29. On solving systems of random linear disequations,
    Quantum Information and Computation 8 (2008), 0579-0594.
    Preprint: arXiv:0704.2988 [quant-ph].
  30. 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.
  31. 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.
  32. Deciding universality of quantum gates,
    J. Algebra 310 (2007), 49-56.
    Preprint: quant-ph/0603009.
  33. Root shadow spaces,
    with Arjeh M. Cohen,
    Europ. J. Combin. 28 (2007), 1419-1441.
    Preprint: pdf at Arjeh.
  34. Root filtration spaces from Lie algebras and abstract root groups,
    with Arjeh M. Cohen,
    J. Algebra 300 (2006) 433-454.
    Preprint: pdf at Arjeh.
  35. 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 Miklos.
  36. 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.
  37. 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
  38. Efficient testing of groups,
    with Katalin Friedl and Miklos Santha.
    Proc. 37th ACM STOC (2005), 157-166.
    Preprint: ps at Miklos.
    MR 2181613
  39. 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
  40. 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
  41. Treating the exceptional cases of the MeatAxe,
    with Klaus Lux
    Experimental Mathematics 9 (2000), 373-381.
    MR 1795309
  42. 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
  43. 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
  44. Finding the radical of matrix algebras using Fitting decompositions,
    Journal of Pure and Applied Algebra 139 (Proc. MEGA'98) (1999), 159-182.
    MR 1700542
  45. 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
  46. 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
  47. 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
  48. 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
  49. 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
  50. Lattice basis reduction for indefinite forms and an application,
    with Ágnes Szántó
    Discrete Mathemathics 153 (1996), 177-188.
    MR 97c:11071
  51. 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
  52. Finding maximal orders in semisimple algebras over Q ,
    with Lajos Rónyai
    Computational Complexity 3 (1993), 245-261.
    MR 95c:11154

Books, book chapters

  1. 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.
  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. Algoritmusok (Algorithms, in Hungarian),
    with Lajos Rónyai and Réka Szabó
    Typotex, Budapest, 1998, 349p.

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.

Unrefereed articles

  1. Chevalley-Warning Theorem in Quantum Computing,
    with Lajos Rónyai. ERCIM News 112 (2018), 28-29.
  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.
  3. Algebra and computation at SZTAKI,
    with Lajos Rónyai and András Benczúr.
    ERCIM News 50 (2002), 31-32.

Some slides

  1. A talk at SIAM AG 2019. Uni Bern, 2019.
  2. A talk at OCIT 2018. IAS, 2018.
  3. Quantum computers, universality, and finite groups , in Hungarian. BME, Budapest, 2013.
  4. On the Euclidean algorithm , in Hungarian. Fazekas Highschool, Budapest, 2012.
  5. Shor's discrete log algorithm , in Hungarian. University of Debrecen, 2011.
  6. On solving disequations , in Hungarian. MTA SZTAKI 2010.
  7. Tutorial lectures on fast quantum algorithms , De Brún Centre for Computational Algebra, Galway, 2009.
  8. Hidden subgroup minicourse , CWI Amsterdam, 2006.
  9. Quantum algorithms for groups, Groups and Probability, Budapest, 2003.
    with Katalin Friedl
    Part II: dvi.gz, ps.gz
    (Part I at Kati: ps.gz .)
Last updated July 9, 2019 by Gábor Ivanyos.