Complexity theory is the area of computer science concerned with the hardness of algorithmic problems, often using complexity classes such as the well known P and NP. There are corresponding complexity classes in quantum computing. We are currently working on the complexity of online problems, problems where the input requests arrive sequentially and each must be serviced with irrevocable decisions before the next request
arrives.
Until recently we were also working on the complexity of Boolean circuits for functions related to cryptology. This included multiplicative complexity, the number of AND gates necessary and sufficient to compute a function using only AND, XOR and NOT gates.
Cryptology involves the design of systems for encryption and decryption, digital signatures, secure protocols, and the possibilities for breaking these systems and protocols. We have worked extensively on zero-knowledge protocols. Current research of the group focus on digital signature schemes, where security against adversaries with (theoretical) access to quantum computing is considered. In addition, a PhD student in the group, Simon Erfurth, wrote an MS thesis concerning the security of a protocol against an adversary with (theoretical) access to quantum computing.
Contact
See more
at the website of the section Algorithms