Seminars

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

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

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

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.

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

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

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

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. We give a simple, fast algorithm for...