Theoretical computer science (TCS) looks at the computational universe around us through the lens of mathematics. The span of problems in TCS include both the design of new models for computational problems as well as the study of efficient algorithms (and computational complexity) for various tasks in well established models. In addition to being central to computer science, in recent decades, TCS has forged strong connections with several areas including biology, economics, physics and law.

The Theory Group at Penn has world-renowned researchers working on core areas of algorithms and complexity as well as applications to areas including algorithmic fairness, cryptography, computational biology, databases, game theory and data privacy.

Recent Events

image from Theory Seminar: Mordecai Golin

Theory Seminar: Mordecai Golin

The speaker for this week’s theory seminar is Mordecai Golin from HKUST. As usual, the talk will take place on Friday 5/5 at 1PM in Levine 307. Title: AIFV-m Coding and Finding the Cheapest Markov Chain Mordecai Golin. Hong Kong UST Abstract: Binary AIFV-m codes are a relatively new method for lossless compression. They encode using an m-tuple of coding trees rather than the single tree used by Huffman coding. Their advantage is better proven redundancy than Huffman codes; their disadvantage is a slight decoding delay.
Read Full Abstract
image from Theory Seminar: Sergei Vassilvitskii

Theory Seminar: Sergei Vassilvitskii

The speaker for the theory seminar on 4/28 is Sergei Vassilvitskii from Google. As usual, the talk will take place at 1pm in Levine 307. Title: New advances in ‘Algorithms with Predictions’ Abstract: The theoretical study of algorithms and data structures has been bolstered by worst-case analysis, where we prove bounds on the running time, space, approximation ratio, competitive ratio, or other measure that holds even in the worst case. In practice, however, we often do not face worst-case scenarios, and the question arises of how we can tune our algorithms to work even better on the kinds of instances we are likely to see, while ideally keeping a rigorous formal framework similar to what we have developed through worst-case analysis.
Read Full Abstract

More

Theory Seminar: Abhishek Shetty

Theory Seminar: Xi Chen

Theory Seminar: Rajesh Jayaram

Theory Seminar: Zihan Tan

All Events