Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Bounds on roots of polynomials (and applications)

Adam Marcus
Princeton University; von Neumann Fellow, School of Mathematics
April 18, 2017
I will discuss methods for deriving bounds on the roots of polynomials, and how one can use such bounds to assert the existence of combinatorial structures with certain spectral properties. This will include introducing the "method of interlacing polynomials" and showing how one can use it prove the existence of Ramanujan graphs. Lastly, I will show how one can interpret these methods as a finite version of the previous week's results.

Efficient empirical revenue maximization in single-parameter auction environments

Yannai Gonczarowski
Hebrew University of Jerusalem and Microsoft Research
April 17, 2017
We present a polynomial-time algorithm that, given samples from the unknown valuation distribution of each bidder, learns an auction that approximately maximizes the auctioneer's revenue in a variety of single-parameter auction environments including matroid environments, position environments, and the public project environment. The valuation distributions may be arbitrary bounded distributions (in particular, they may be irregular, and may differ for the various bidders), thus resolving a problem left open by previous papers.

Noncommutative probability for computer scientists

Adam Marcus
Princeton University; von Neumann Fellow, School of Mathematics
April 11, 2017
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 things related to random matrices (asymptotically as the size of the matrices get large). This will include introducing the concept of free independence and seeing how it compares to classical independence. No prior knowledge will be assumed.

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.