Bureaucrats, editor, Administrators
28
edits
Changes
From Theory
no edit summary
<br>
<br>
Cryptography began as a rigorous formalization of issues arising in data and computer security (encryption, authentication, etc.), but has since expanded to touch upon many other areas of theoretical computer science (the most striking example being the concept of "zero-knowledge proofs"). Research at UMD explores both the practical and the theoretical aspects of this field. A primary motivation is to understand the <em>efficiency</em> of cryptographic solutions by (1) improving the computational/communication complexity of existing protocols, (2) using new number-theoretic assumptions to speed up current constructions, (3) designing improved algorithms for faster computation, and (4) proving lower bounds on the best possible efficiency that can be achieved.
Cryptography began as a rigorous formalization of issues arising in data and computer security (encryption, authentication, etc.), but has since expanded to touch upon many other areas of theoretical computer science (the most striking example being the concept of "zero-knowledge proofs"). Research at UMD explores both the practical and the theoretical aspects of this field. A primary motivation is to understand the <em>efficiency</em> of cryptographic solutions by (1) improving the computational/communication complexity of existing protocols, (2) using new number-theoretic assumptions to speed up current constructions, (3) designing improved algorithms for faster computation, and (4) proving lower bounds on the best possible efficiency that can be achieved.
<br><br>
<li> Fixed-Parameter Algorithms:
[http://www.cs.umd.edu/~hajiagha/ Mohammad Hajiaghayi]
<br>
Fixed-parameter algorithms (a.k.a. parameterized complexity) is another approach to cope with hardness of NP-complete problems. In these algorithms, we allow the running time to be exponential, but only with respect to a parameter other than
the problem size, while the result must be optimal (the parameter is
often small in practice). In particular, parameterized complexity uses a set of techniques
such as kernelization, bounded search trees, bounded treewidth of graphs, and extremal combinatorics among others. Though until recently, approximation algorithms and fixed-parameter algorithms have been considered to be two different approaches with different methodology that have very little to
do with each other, very recently several connections
between the two fields were identified. We are currently investigating these connections along with traditional parameterized algorithms for NP-complete problems.
<br><br>
<br><br>
