# Computer Science and Discrete Mathematics (CSDM)

## Some basic problems and results from Invariant Theory

Invariant theory deals with properties of symmetries - actions of groups on sets of objects.

It has been slower to join its sibling mathematical theories in the computer science party, but we now see it more and more in studies of computational complexity, pseudorandomness, and the analysis of algorithms.

## Interactive coding with nearly optimal round and communication blowup

The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since these seminal works, there have been many follow-up works which improve the error rate, the communication rate, and the computational efficiency.

## Structural and computational aspects of Brascamp-Lieb inequalities

## New insights on the (non)-hardness of circuit minimization and related problems

## A unified duality-based approach to Bayesian mechanism design

We provide a duality framework for Bayesian Mechanism Design. Specifically, we show that the dual problem to revenue maximization is a search over *virtual transformations.* This approach yields a unified view of several recent breakthroughs in algorithmic mechanism design, and enables some new breakthroughs as well. In this talk, I'll:

1) Provide a brief overview of the challenges of multi-dimensional mechanism design.

2) Construct a duality framework to resolve these problems.