Gabor Ivanyos
Visiting Research Associate Professor
Miklos Santha


  • Youming Qiao, G. Ivanyos. Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing.
  • G. Ivanyos, Péter Kutas, Lajos Rónyai. Computing explicit isomorphisms with full matrix algebras over $\mathbb{F}_q(x)$.
  • G. Ivanyos, Youming Qiao, K. V. Subrahmanyam. Constructive noncommutative rank computation in deterministic polynomial time over fields of arbitrary characteristics.


  • G. Ivanyos, Youming Qiao, K. V. Subrahmanyam. (2017). On generating the ring of matrix semi-invariants. Computational Complexity 26 717-763
  • M. Santha, Y. Qiao, G. Ivanyos, A. Belovs, S.Yang. (2017). On the Polynomial Parity Argument complexity of the Combinatorial Nullstellensatz. Proceedings of the 32nd Computational Complexity Conference 30
  • G. Ivanyos, M. Santha. (2017). On solving systems of diagonal polynomial equations over finite fields. Theoretical Computer Science 657 73-85
  • Frederic Magniez, Ashwin Nayak, M. Santha, Jonah Sherman, G. Ivanyos, David Xiao. (2016). Improved bounds for the randomized decision tree complexity of recursive majority. Random Structures and Algorithms 48 612-638
  • Katalin Friedl, G. Ivanyos, Frederic Magniez, M. Santha, Pranab Sen. (2014). Hidden Translation and Translating Coset in Quantum Computing. SIAM Journal of Computing 43 1-24
  • T. Decker, P. Hoyer, G. Ivanyos, M. Santha. (2014). Polynomial time quantum algorithms for certain bivariate hidden polynomial problems. Quantum Information and Computation 14 790–806
  • T. Decker, G. Ivanyos, R. Kulkarni, Y. Qiao, M. Santha. (2014). An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group. International Symposium MFCS 226-238
  • G. Ivanyos, R. Kulkarni, Y. Qiao, M. Santha, A. Sundaram. (2014). On the complexity of trial and error for constraint satisfaction problems. Proceedings of ICALP 663-675
  • G. Ivanyos, Marek Karpinski, Y. Qiao, M. Santha. (2014). Generalized Wong sequences and their applications to Edmonds. Proceedings of STACS 25 397-408
  • T. Decker, G. Ivanyos, M. Santha, Pawel Wocjan. (2013). Hidden Symmetry Subgroup Problems. SIAM Journal of Computing 42 1987-2007
  • G. Ivanyos, H. Klauck, T. Lee, M. Santha, Ronald de Wolf. (2012). New bounds on the classical and quantum communication complexity of some graph properties. Proceedings of FSTTCS 148-159
  • G. Ivanyos, Luc Sanselme, M. Santha. (2012). An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups. Algorithmica 62 480-498
  • G. Ivanyos, M. Karpinski, N. Saxena. (2010). Deterministic polynomial time algorithms for matrix completion problems. SIAM Journal of Computing 39 3736-3751
  • G. Ivanyos, M. Karpinski, N. Saxena. (2009). Schemes for deterministic polynomial factoring. ISSAC 191-198
  • G. Ivanyos, A.B. Nagy, L. Rónyai. (2008). Constructions for quantum computing with symmetrized gates. Quantum Information and Computation 8 0411-0429
  • G. Ivanyos. (2008). On solving systems of random linear disequations. Quantum Information and Computation 8 0579-0594
  • G. Ivanyos, Marek Karpinski, M. Santha, Nitin Saxena, Igor Shparlinski. Polynomial Interpolation and Identity Testing from High Powers over Finite Fields. Algorithmica