Computational Complexity

Computational complexity theory studies the inherent difficulty of mathematical and logical problems and classifies them based on the time and memory resources required to solve them. It then seeks to understand the relationships between these classifications. At the heart of this field lies the famous P versus NP problem, which explores whether every problem whose solution can be quickly verified can also be quickly solved by a computer. Our research involves study of complexity measured for various models of computation including Boolean circuits, arithmetic circuits and communication complexity. Over the recent years, our group is mainly focused on complexity measures of Boolean functions, pseudo randomness, algorithmic issues related to Boolean and arithmetic circuits.