Bayesian optimization (BO) is a powerful tool for sequentially optimizing black-box functions that are expensive to evaluate, and has extensive applications including automatic hyperparameter tuning, environmental monitoring, and robotics. The problem of level-set estimation (LSE) with Gaussian processes is closely related; instead of performing optimization, one seeks to classify the whole domain according to whether the function lies above or below a given threshold, which is also of direct interest in applications.

In this talk, we present a new algorithm, truncated variance reduction (TruVaR) that addresses Bayesian optimization and level-set estimation in a unified fashion. The algorithm greedily shrinks a sum of truncated variances within a set of potential maximizers (BO) or unclassified points (LSE), which is updated based on confidence bounds. TruVaR is effective in several important settings that are typically non-trivial to incorporate into myopic algorithms, including pointwise costs, non-uniform noise, and multi-task settings. We provide a general theoretical guarantee for TruVaR covering these phenomena, and use it to obtain regret bounds for several specific settings. We demonstrate the effectiveness of the algorithm on both synthetic and real-world data sets.

The Algebraic Eraser is a cryptosystem (more precisely, a class of key
agreement schemes) introduced by Anshel, Anshel, Goldfeld and Lemieux
about 10 years ago. There is a concrete instantiation of the Algebraic
Eraser called the Colored Burau Key Agreement Protocol (CBKAP), which
uses a blend of techniques from permutation groups, matrix groups and
braid groups. SecureRF, the company owning the trademark to the
Algebraic Eraser, is marketing this system for lightweight
environments such as RFID tags and other Internet of Things
applications; they have proposed making this scheme the basis for an
ISO RFID standard.

This talk gives an introduction to the Algebraic Eraser, a brief
history of the attacks on this scheme using ideas from group-theoretic
cryptography, and describes the countermeasures that have been
proposed. I would not recommend the scheme for the proposed
applications: the talk ends with a brief sketch of a recent convincing
cryptanalysis of this scheme due to Ben-Zvi, Blackburn and Tsaban
(which appeared at CRYPTO this summer), and significant attacks
on the protocol in the proposed ISO standard due to Blackburn and
Robshaw (which appeared at ACNS earlier this year).