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