Computer Science/Discrete Mathematics

Date:
Sep
20
2021

Computer Science/Discrete Mathematics Seminar I

Expander Random Walks: A Fourier-Analytic Approach
11:15am|Simonyi Hall 101 and Remote Access

A random walk on expanders, despite its strong underlying correlations, poses extremely useful pseudorandom properties. The expander hitting property and the expander Chernoff are two such classic examples. That is, the AND function and certain...

Sep
21
2021

Computer Science/Discrete Mathematics Seminar II

Linear spaces of matrices
10:30am|Simonyi Hall 101 and Remote Access

The study of linear spaces of matrices arises naturally (and independently) in many different areas of mathematics and computer science.  In this survey talk, I will describe some of these motivations, and state and prove some (old and new)...

Sep
27
2021

Computer Science/Discrete Mathematics Seminar I

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits I : An overview
11:15am|Simonyi Hall 101 and Remote Access

Every multivariate polynomial P(x_1,...,x_n) can be written as a sum of monomials, i.e. a sum of products of variables and field constants.  In general, the size of such an expression is the number of monomials that have a non-zero coefficient in P...

Sep
28
2021

Computer Science/Discrete Mathematics Seminar II

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits II : A more detailed approach
Sébastien Tavenas
10:30am|Simonyi Hall 101 and Remote Access

Every multivariate polynomial P(x_1,...,x_n) can be written as a sum of monomials, i.e. a sum of products of variables and field constants.  In general, the size of such an expression is the number of monomials that have a non-zero coefficient in P...