Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

In pursuit of obfuscation

Allison Bishop
Columbia University
April 10, 2017
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 knowledge on obfuscation will be assumed. We will end with some open directions that should be accessible to theoreticians outside of cryptography.

A time-space lower bound for a large class of learning problems

Ran Raz
Princeton University
April 3, 2017

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 special case, this gives a new proof for the time-space lower bound for parity learning [R16].

Applications of monotone constraint satisfaction

Robert Robere
University of Toronto
March 28, 2017

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.

Applications of monotone constraint satisfaction

Robert Robere
University of Toronto
March 27, 2017

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.

Approximate counting and the Lovasz local lemma

Ankur Moitra
Massachusetts Institute of Technology
March 20, 2017

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.

Some basic problems and results from Invariant Theory

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
March 7, 2017

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

Yael Kalai
Microsoft Research
March 6, 2017

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

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
February 28, 2017
The celebrated Brascamp-Lieb (BL) inequalities are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory, with many used in computer science. I will survey the well-understood structural theory of BL inequalities, and then discuss their computational aspects. Far less was known about computing their main parameters, and I will discuss new efficient algorithms (via operator scaling) for those, which also inform structural questions.