Seminars

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

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

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 will give a high-level overview of computable analysis---an area studying the computational properties of continuous objects such as functions and measures on $\mathbb R^d$. We will then discuss some applications to the computability and...

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

Combinatorial geometry is a field that studies combinatorial problems that involve some simple geometric objects/notions, such as: lines, points, distances, collinearity. While such problems are often easy to state, some of them are very difficult...

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