Personal tools
You are here: Home People Research Research Topics Theoretical Computer Science

Theoretical Computer Science

Faculty working in theoretical computer science apply mathematical foundations and techniques to study, understand, explain, and solve a wide range of problems fundamental to computing. They support the educational mission of the department through instruction in core and advanced principles of computer science. Their research advances the basic knowledge of computing and directly supports applied research areas. The expertise of the faculty includes graph algorithms, approximation algorithms, sublinear-time algorithms, computational complexity, randomized algorithms, computational geometry, coding theory, computational molecular biology, cryptography, privacy, computational logic, type theory, and programming languages semantics. Their work has connections to diverse applications such distributed databases, property testing, biological computing, information theory, combinatorics, quantum mechanics, program verification, and compiler technology.

Theoretical Computer Science Group

Currently, the research focuses on designing improved algorithms and understands the reasons for the computational difficulties in solving the graph isomorphism problem. The focus is on discrete combinatorial methods. Closely related to the graph isomorphism problem is the fundamental task of choosing names for finite structures (e.g., molecules) that are efficiently computable. Research also focuses on design and analysis of algorithms to deal with computationally hard problems. It is conjectured that NP-hard optimization problems don't allow any computationally efficient exact solutions. Therefore, the goal is either to design efficient algorithms producing solutions which are provably close to optimal, or proving that for certain problems no such algorithms exist. 

Programming Languages - Investigator: Professor Kandemir 

The programming languages/compiler research at Penn State explores language and compiler support for diverse computing systems, including battery-operated embedded systems, unmanned underwater and aerial vehicles, and disk-intensive operating environments. The common theme exploited in these efforts is to expose the architectural and environmental/operational conditions to the compiler in the form of high level abstractions and let the compiler perform its optimizations and code/data restructuring based on these abstractions. In embedded systems, these abstractions capture the power reduction capabilities of the underlying system; in unmanned vehicles, they contain vehicle types and capabilities; and in disk-intensive environments, they capture storage characteristics. The optimization metrics targeted by this research include performance, energy consumption, memory space requirements, and reliability. Our research also defines the role of the compiler as the tool that reconfigures the hardware and optimizes the code based on reconfiguration, as opposed to a more conventional role of pure code optimization.

Document Actions