Computing a fixed point of contraction maps in polynomial queries @SimonsInstituteTOC

Simons Institute | Computing a fixed point of contraction maps in polynomial queries @SimonsInstituteTOC | Uploaded 2 months ago | Updated 22 hours ago
Yuhao Li (Columbia)
https://simons.berkeley.edu/talks/yuhao-li-columbia-2024-07-17
Games and Equilibria in System Design and Analysis

It is well known that solving simple stochastic games, whose complexity remains a long-standing open problem, can be reduced to computing a fixed point of contraction maps. In this talk, we consider general algorithms that access the contraction map in a black-box manner (as an oracle). We show a positive result -- a query-efficient algorithm for computing a fixed point of contraction maps, which may be interpreted as evidence supporting that contraction fixed point/simple stochastic games might be computationally tractable.

[Joint work with Xi Chen and Mihalis Yannakakis]

Bioacoustics and Machine Learning as Key Tools in Conservation

$Hypothesis selection with computational constraints Maryam Aliakbarpour (Rice University) https://simons.berkeley.edu/talks/maryam-aliakbarpour-rice-university-2024-06-21 Extroverted Sublinear Algorithms Hypothesis selection is a fundamental problem in learning theory and statistics. Given a dataset and a finite set of candidate distributions, the goal is to select a distribution that matches the data as well as possible. More specifically, suppose we have sample access to an unknown distribution $P$ over a domain $mathcal{X}$. We assume that $P$ is well-approximated by one of $n$ distributions in a class (called hypotheses), denoted $mathcal{H} coloneqq {H_1, H_2, ldots, H_n}$. The goal is to design an algorithm that outputs a distribution $hat{H} in mathcal{H}$ whose total variation distance from $P$ is nearly minimal. In this work, we study the hypothesis selection problem under memory and time constraints. In particular, we discuss how to achieve a nearly optimal tradeoff between memory usage and sample complexity. Additionally, we explore methods to obtain optimal accuracy via algorithms with nearly optimal time complexity.$

Lessons from Texas, COVID-19, and the 737 Max: Efficiency vs. Resilience | Richard M. Karp...

Conditional Sampling for Distribution Testing

Sparsifying Set Systems for Coverage Problems

A Strong Separation for Adversarially Robust L_0 Estimation for Linear Sketches

Deciding regular games: a playground for exponential time algorithms

Descriptive complexity for distributed computing and neural networks