The Theory area studies the fundamentals of computation. These fundamentals include complexity theory to determine the inherent limits of computation and communication and cryptography and the design and analysis of algorithms to obtain optimal solutions within those limits.
- Prof. Edith Hemaspaandra
- Prof. Ivona Bezáková
- Prof. Chris Homan
- Prof. Hadi Hosseini
- Prof. Stanislaw P. Radziszowski
The THEORY CANAL meeting (the Rochester Theory Seminar) is a joint project of the RIT and UR theory groups, and the focus is all areas of theoretical computer science. THEORY CANAL meets (when RIT and UR classes are in session) on the second and fourth Wednesdays of each month. Click here for more info on the series and the schedule of speakers.
Selected Research Projects
Computational Ramsey Theory
Ramsey theory is often regarded as the study of how order emerges from randomness. It has applications in parallel programming, approximation algorithms, game theory, geometry, number theory, and other areas of mathematics and theoretical computer science. The determination of whether many Ramsey properties hold is notoriously difficult. The goal of our research is to enhance known and develop new theoretical and computational methods solving Ramsey-type problems.
Computational Social Choice
Elections are broadly used in both human and computational settings, including a rapidly expanding range of applications in multiagent systems. It has been known since the mid-1970s (the Gibbard-Satterthwaite Theorem) that every reasonable election system has instances on which voters have an incentive to vote strategically. Computational social choice seeks to sidestep that impossibility result by making manipulation not impossible but rather computationally prohibitive.
Computational social network analysis| (CSNA)
This work combines social media, network science, sociology, and advanced computational methods to study social networks and the roles they play in organizational behavior, motivated by the belief that a better understanding of those dynamics will lead to better health, productivity, and general social welfare.