Computer Science Group

Quantum mechanics and computer science are two of the biggest developments in the last century in science and technology: quantum mechanics gave us the opportunity to understand nature at the nanoscale, where the laws of physics are fundamentally different from the conventional (classical) physics; information technologies have revolutionized our everyday lives.

Quantum computing and quantum information science bring these fields together, applying quantum mechanics to problems in computing and communication. After Shor’s 1994 discovery of a quantum algorithm for factoring integers, which threatened the security of a widely-used encryption method, interest in quantum information science thrived. Other achievements of quantum information science include efficient and secure protocols for communication and cryptography. Those protocols have already resulted in quantum cryptography devices that are commercially available.

The computer science group’s activity covers a wide range of areas in quantum computing and information theory, often in close connection with related research areas in classical theoretical computer science. We mostly investigate quantum algorithms, complexity and quantum-safe cryptography. Quantum algorithms provide a recipe for efficiently solving practical problems on a quantum computer, of particular interest are problems which are difficult to solve on a classically. The study of quantum computational complexity is about understanding the fundamental limitations of information processing tasks in nature. By understanding such limits, it can offer a guide to crafting new algorithms and communication protocols. Quantum-safe cryptography is concerned with the design and the evaluation of cryptographic systems which are resistant even to quantum attacks.

More information at our homepage:

Group Members

Recent papers

  • M. Santha, Youming Qiao, Raghav Kulkarni, Gábor Ivanyos, Aarthi Sundaram. (2018). On the Complexity of Trial and Error for Constraint Satisfaction Problems. Journal of Computer and System Sciences 92 48-64
  • Kaspars Balodis, M. Santha, Juris Smotrovs, T. Lee, Aleksandrs Belovs, Andris Ambainis. (2017). Separations in Query Complexity Based on Pointer Functions. JACM 64
  • Yixin Shen, Rajendra Kumar, Yanlin Chen, D. Aggarwal. Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding.
  • Mark Simkin , Joao Ribeiro, Maciej Lukasz Obremski, D. Aggarwal, Luisa Siniscalchi. Computational and Information-Theoretic Two-Source (Non-Malleable) Extractors.
  • Youming Qiao, Gábor Ivanyos. (2019). Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing. SIAM Journal of Computing
  • Lajos Rónyai, Péter Kutas, Gábor Ivanyos. (2019). Explicit equivalence of quadratic forms over $\\\\mathbb{F}_q(t)$. Finite Fields and Their Applications
  • D. Aggarwal, Maciej Lukasz Obremski. Inception makes non-malleable codes shorter as well!.
  • Jesper Buus Nielsen, Ivan Damgard, Maciej Lukasz Obremski, D. Aggarwal, E. Purwanto, Mark Simkin, Joao Ribeiro. (2019). Stronger Leakage-Resilient and Non-Malleable Secret-Sharing Schemes for General Access Structures. Proceedings of CRYPTO
  • Nico Dottling, D. Aggarwal, E. Purwanto, Maciej Obremski, Jesper Buus Nielsen. (2019). Continuous non-malleable codes in the 8-split-state model. Springer EUROCRYPT 531-561
  • Swagato Sanyal, M. Santha, T. Lee, D. Gavinsky. (2019). A composition theorem for randomized query complexity via max conflict complexity. Automata, Languages, and Programming
  • M.Ray, M. Santha, T. Lee. (2019). Strategies for quantum races. ITCS 14
  • M. Santha, T. Lee, Gavin K. Brennen, D. Aggarwal, M. Tomamichel. (2018). Quantum attacks on Bitcoin, and how to protect against them. Ledger 3
  • Aarthi Sundaram, Jamie Sikora, M. Santha, Sevag Gharibian, Justin Yirka. (2018). Quantum generalizations of the polynomial hierarchy with applications to QMA(2). International Symposium MFCS 1-16
  • Gábor Ivanyos, Péter Kutas, Lajos Rónyai. (2019). Explicit equivalence of quadratic forms over $\\mathbb{F}_q(t)$. Finite Fields and Their Applications 55 33-63
  • Lajos Rónyai, Péter Kutas, Gábor Ivanyos. (2018). Computing explicit isomorphisms with full matrix algebras over $\mathbb{F}_q(x)$. Foundations of Computational Mathematics 18 381-397
more preprints > more publications >