Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Structural aspects of the null-cone problem in invariant theory

Ankit Garg
Microsoft Research
October 10, 2017
Invariant theory studies the actions of groups on vector spaces and what polynomial functions remain invariant under these actions. An important object related to a group action is the null cone, which is the set of common zeroes of all homogeneous invariant polynomials. I will talk about the structural aspects of the null cone from a computational and optimization perspective. These will include the Hilbert-Mumford and Kempf-Ness theorems which imply that null cone membership is in NP intersect coNP (ignoring bit-size issues).

Barriers for rank methods in arithmetic complexity

Rafael Oliveira
University of Toronto
October 9, 2017

Arithmetic complexity is considered (for many good reasons) simpler to understand than Boolean complexity. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than in Boolean complexity. Despite many successes and rapid progress, however, foundational challenges, like proving super-polynomial lower bounds on circuit or formula size for explicit polynomials, or super-linear lower bounds on explicit 3-dimensional tensors, remain elusive.

Elementary open problems in Algebra (with consequences in computational complexity)

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
October 3, 2017
I will survey some elementary (to state!) problems on groups, matrices, and tensors, and discuss their motivations arising from several major problems in computational complexity theory. On each problem there was some exciting recent progress which may raise hope it can be resolved. No special background will be assumed.

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.