Some fact about Complexity, Algorithms, Cryptography

• Computational Complexity

Most of the open problems in computational complexity can be stated in terms of lower bounds. There are few general techniques available in proving lower bounds, and consequently, there has been little progress in this field. My approach to solving such problems is bottom up, working with simple open problems such as:

• Do we need an exponential number of states to simulate a two-way nondeterministic finite automaton by a deterministic one?
• What is the minimum parallel time required to solve some specific problems using a given number of processors? 

• Algorithms

  I am working on designing new sequential and parallel algorithms, and improving existing ones, to solve various computational problems such as: graph isomorphism, membership in permutation groups (generalized Rubik's Cube), network flow, matching in graphs, Boolean matrix multiplication, and connectivity of graphs.
  Recently, I have been concentrating on the following problems.
  Dynamic graph algorithms. These are algorithms which solve problems in which the input graph keeps changing; e.g. edges are inserted and deleted or weights are increased or decreased. The goal is to maintain the solution in such a way that the changes in it can be found faster than resolving the problem from scratch.
  String processing algorithms with applications to molecular biology. There exist computational problems associated with the human genome project where algorithmic improvements are possible. An area were considerable progress has already been achieved is the speed up of various dynamic programming techniques.
   

• Cryptography

  Various number theoretic problems, such as factoring of integers, primality testing, discrete logarithms and quadratic residuocity, are used as a basis for public key cryptosystems. The security of such crpytosystems therefore depends on the complexity of these problems. A deeper understanding of the complexity of these problems can help in reasoning about the security of the cryptosystems.
  Currently, proving the correctness and security of cryptoprotocols is hard. I am working on general techniques that can be applied to constructing protocols for which it is possible to prove things about.