Computer Science and Discrete Mathematics (CSDM)

I will give an introduction to computational techniques in noncommutative probability for people (like myself) that are less interested in the details of the theory and more interested using results in the theory to help understand the behavior of...

This talk will survey some recent advances in research on program obfuscation, an area of theoretical cryptography that has seen unprecedented levels of activity over the last four years. We will cover material starting from the basics, and no prior...

We prove a general time-space lower bound that applies for a large class of learning problems and shows that for every problem in that class, any learning algorithm requires either a memory of quadratic size or an exponential number of samples. As a...

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...

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...

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...

Indistinguishability obfuscation has turned out to be an outstanding notion with strong implications not only to cryptography, but also other areas such as complexity theory, and differential privacy. Nevertheless, our understanding of how to...

The computational complexity of finding Nash Equilibria in games has received much attention over the past two decades due to its theoretical and philosophical significance. This talk will be centered around the connection between this problem and...

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...

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...