Seminars

Apr
18
2017

Computer Science/Discrete Mathematics Seminar II

Bounds on roots of polynomials (and applications)
10:30am
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...
Apr
17
2017

Computer Science/Discrete Mathematics Seminar I

Efficient empirical revenue maximization in single-parameter auction environments
Yannai Gonczarowski
11:15am
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...
Apr
11
2017

Computer Science/Discrete Mathematics Seminar II

Noncommutative probability for computer scientists
10:30am
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...
Apr
10
2017

Computer Science/Discrete Mathematics Seminar I

In pursuit of obfuscation
Allison Bishop
11:15am
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...
Apr
04
2017

Computer Science/Discrete Mathematics Seminar II

Computability and complexity in analysis and dynamics
10:30am
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...
Apr
03
2017

Computer Science/Discrete Mathematics Seminar I

A time-space lower bound for a large class of learning problems
11:15am
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...
Mar
28
2017

Computer Science/Discrete Mathematics Seminar II

Applications of monotone constraint satisfaction
10:30am
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...
Mar
27
2017

Members' Seminar

Extremal problems in combinatorial geometry
Orit Raz
2:00pm
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...
Mar
27
2017

Computer Science/Discrete Mathematics Seminar I

Applications of monotone constraint satisfaction
11:15am
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...
Mar
20
2017

Computer Science/Discrete Mathematics Seminar I

Approximate counting and the Lovasz local lemma
11:15am
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...