Theoretical Foundations 

Theoretical foundations of Computer Science and Engineering include mathematically provable design of computer systems and methods. Theoretical analysis is important in proving correctness of computer systems. Algorithms with provable efficiency guarantees form building blocks for solutions to complex problems especially those involving bigdata. The efficiency can be in terms of time, network bandwidth, Input/Output bottlenecks, disk space or memory usage and/or energy. These algorithms have applications to virtually every subfield of computer science like optimization, information retrieval, databases, networking, vision, and computational biology. Semantic analysis forms the backbone of software systems. Several faculty work on different aspects of algorithms, data structures and formal analysis. Areas of interest include: Network Optimization and Graph Algorithms; Game Theory; Online Algorithms and Scheduling; Semantics and Program Analysis; I/O efficient data structures; Algorithms for string matching; Distributed and Parallel Computing.

Faculty

Rahul Shah: Disk-Bound Algorithms, Data Structures

Evangelos Triantaphyllou: Optimization

Specific Projects

Distributed algorithms and data structures. Busch designs and analyzes protocols for the distributed coordination of network nodes in order to solve efficiently routing problems, distributed directories, counting problems, data streaming algorithms, buy-at-bulk network design problems, and oblivious data structures such as universal Steiner trees. Funded by NSF-CNS.

Algorithmic game theory. Busch explores the impact of non-coordinated strategic actions of selfish players in network congestion games and measure their impact in stable states, Nash Equilibria, with the metrics of price of anarchy and price of stability. They have shown surprising results where selfishness does not harm the social welfare. Supported by NSF-CNS.

Graph algorithms. Kundu works on distributed graph algorithms with applications in robotics.

Program analyses. Mukhopadhyay performs automated termination and complexity analyses of programs, and model-based static analysis. Supported by NSF.

Pattern matching for massive data sets. Shah develops new indexes and methods for storing and querying massive string (biological) data which resides on disks. Space compression, I/O bottlenecks are primary performance metrics. Supported by NSF-CCF.

Multi-pattern matching in text streams. Shah focuses on finding patterns in streaming data which cannot be stored and can be seen only in one pass. Moreover, only a sketch of patterns can be stored in memory. This has direct applications in intrusion detection at router level and anti-virus softwares. Supported by NSF-CCF.

Multi-class classification. Triantaphyllou develops new methods for multi-class classification when the classes are ordinal. Available multi-class classifiers do not explicitly take into consideration the fact that in many cases the classes can be ordered. Doing this may improve classification accuracy quite impressively. He explores under what conditions the proposed approach should be used and applies it to real world data where the assumptions are met partially, still outperforming existing ones.