Recently, a certain "monotone" version of the constraint satisfaction problem has proved an extremely useful tool for attacking problems in circuit, communication, and proof complexity theory. In this talk we discuss this version of the constraint satisfaction problem and touch on its connection to fundamental lower-bounds problems in these areas. We also consider a recent and interesting application: the first exponential lower bounds on the length of cutting planes refutations of random CNF formulas.
Computer Science and Discrete Mathematics (CSDM)
We introduce a new approach for approximately counting in bounded degree systems with higher-order constraints. Our main result is an algorithm to approximately count the number of solutions to a CNF formula where the degree is exponential in the number of variables per clause. Moreover our algorithm extends straightforwardly to approximate sampling, which shows that under Lovasz Local Lemma-like conditions, it is possible to generate a satisfying assignment approximately uniformly at random.
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.
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.
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.