Seminars

Oct
30
2017

Computer Science/Discrete Mathematics Seminar I

Fooling intersections of low-weight halfspaces
Rocco Servedio
11:00am

A weight-$t$ halfspace is a Boolean function $f(x)=\mathrm{sign}(w_1 x_1 + \cdots + w_n x_n - \theta)$ where each $w_i$ is an integer in $\{-t,\dots,t\}.$ We give an explicit pseudorandom generator that $\delta$-fools any intersection of $k$ weight-...

Oct
24
2017

Computer Science/Discrete Mathematics Seminar II

On the strength of comparison queries
10:30am

Joint work with Daniel Kane (UCSD) and Shachar Lovett (UCSD)We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.For example, for any constant $k$, we construct linear decision...

Oct
23
2017

Computer Science/Discrete Mathematics Seminar I

A nearly optimal lower bound on the approximate degree of AC$^0$
Mark Bun
11:00am

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. For any constant $\delta > 0$, we exhibit an AC$^0$ function of approximate degree $\Omega(n^{1-\delta}...

Oct
16
2017

Theoretical Machine Learning Seminar

Keeping IT cool: machine learning for data center cooling
Nevena Lazic
12:30pm

I will describe recent efforts in using machine learning to control cooling in Google data centers, as well as related research in linear quadratic control.

Oct
10
2017

Computer Science/Discrete Mathematics Seminar II

Structural aspects of the null-cone problem in invariant theory
Ankit Garg
10:30am

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

Oct
09
2017

Computer Science/Discrete Mathematics Seminar I

Barriers for rank methods in arithmetic complexity
Rafael Oliveira
11:00am

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

Oct
03
2017

Computer Science/Discrete Mathematics Seminar II

Elementary open problems in Algebra (with consequences in computational complexity)
10:30am

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

Oct
02
2017

Theoretical Machine Learning Seminar

Hyperparameter optimization: a spectral approach
Elad Hazan
12:30pm

Modern machine learning algorithms often involve complicated models with tunable parameters, called hyperparameters, that are set during training. Hyperparameter tuning/optimization is considered an art. (See e.g. http://www.argmin.net/2016/06/20...