Uncertainty in Computation 2016
2016-10-04..2016-10-07
Berkeley, United States
[Learning, Algorithm Design and Beyond Worst-Case Analysis, Quantifying Uncertainty: Stochastic, Adversarial, and Beyond, Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016), Probabilistic Circuits and Logic 2023, ITCS 2023, Rigorous Evidence for Information-Computation Trade-offs]
as the organisers put it
Classical approaches to algorithm design are both over-pessimistic (in making worst-case assumptions about the input) and over-optimistic (in assuming that the input is completely specified). This program explores alternatives to worst-case analysis of algorithms, as well as new methods for addressing uncertainty in instance specifications, with reference to a broad range of applications in learning, optimization and control.
| title | author | length |
|---|---|---|
| Unifying Logic and Probability: The BLOG Language | Stuart Russell | 01h 01m |
Presents BLOG, an open-universe semantics probabilistic language that lets models create and delete objects via number statements, so identity and count are… | ||
| Model Checking and Strategy Synthesis for Stochastic Games: From Theory to Practice | Marta Kwiatkowska | 43m |
Extension of PRISM implements turn-based stochastic multiplayer games and a temporal logic called RP-ATL to specify probabilistic and reward objectives and to… | ||
| Computing Probabilistic Bisimilarity Distances via Policy Iteration | Franck van Breugel | 37m |
Defines probabilistic bisimilarity distance as the least fixed‑point Kantorovich/earth‑mover metric via coupling vertices, shows it reduces to a finite… | ||
| Quantitative Algebraic Reasoning | Radu Mardare | 43m |
Defines a quantitative equational logic where equations are s =ε t (distance ε) and replaces congruence by nonexpansiveness, builds term pseudometrics and… | ||
| Controlling Probabilistic Systems Under Partial Observation | Nathalie Bertrand | 43m |
Uses Rabin probabilistic automata and partially observable Markov decision processes to pin down what is decidable: emptiness/threshold problems are broadly… | ||
| Three Problems in Computable Probability Theory | Cameron E. Freer | 55m |
Proves that an exchangeable sequence with a computable law yields a computable mixing measure via effective moment approximations and uniform procedures; shows… | ||
| Brief Tutorial on Probabilistic Databases | Dan Suciu | 01h 01m |
Defines a tuple-independent model where each tuple is a random event and query probability equals the probability of the lineage (grounded FO sentence) and… | ||
| A Dichotomy for Queries with Negation in Probabilistic Databases | Dan Olteanu | 43m |
Proves a dichotomy for nonrepeating relational-algebra queries with set difference over tuple‑independent probabilistic databases: either evaluation is… | ||
| Fourier Representations in Probabilistic Inference | Bart Selman | 31m |
Claim: Boolean probability tables for bounded‑width factor graphs have most L2 mass on low‑degree Hadamard/Fourier basis coefficients, so truncating high‑order… | ||
| Approximate Lifted Inference with Probabilistic Databases | Wolfgang Gatterbauer | 47m |
Presents an approximate inference pipeline that converts query lineage into compact representations and then applies sampling plus structural shortcuts to… | ||
| Scalable Collective Inference from Richly Structured Data using Probabilistic Soft Logic (PSL) | Lise Getoor | 41m |
A probabilistic programming framework maps weighted logical rules over richly relational data to a convex optimization by treating random variables as… | ||
| Stochastic Control via Entropy Compression | Dimitris Achlioptas | 42m |
Introduces a flows-action framework that turns Moser’s local-resampling into a general stochastic-control algorithm, proves a cutoff-style convergence when… | ||
| Probabilistic Reasoning by First-Order Model Counting | Guy Van den Broeck | 48m |
Weighted first‑order model counting (WFOMC) reduces Markov logic networks to a sentence plus a weight function and exploits weight symmetry to perform lifted… | ||
| A Personal Viewpoint on Probabilistic Programming | Daniel Roy | 01h 03m |
Argues that probabilistic programs represent distributions by sample-generating code and that Bayesian conditioning can be phrased as conditioning as program… | ||
| Probabilistic Programming for Augmented Intelligence | Vikash K. Mansinghka | 40m |
Probabilistic programming systems build two working tools: Picture, a Julia-embedded vision pipeline that combines a differentiable renderer, a… | ||
| Differential Privacy | Kunal Talwar | 42m |
Survey of real attacks shows reidentification from anonymized records (Massachusetts medical release, Netflix Prize, GWAS/Homer). Formal guarantee treats the… | ||
| Pufferfish Privacy Mechanisms for Correlated Data | Kamalika Chaudhuri | 43m |
Proposes a concrete privacy framework for correlated data and two mechanisms: the Wasserstein mechanism uses the infinity-Wasserstein distance as an analog of… | ||
| Axioms for Information Leakage | Catuscia Palamidessi | 41m |
Claims that a small set of intuitive axioms (continuity, convexity/monotonicity, and a data‑processing-like property) exactly characterizes vulnerability… | ||
| Constrained Sampling and Counting | Moshe Vardi | 46m |
Describes an implementation that turns universal hashing plus XOR constraints into a practical sampler and counter: uses Crypt minisat to handle CNF+XOR… | ||
| Learning about Auctions | Avrim Blum | 43m |
Reconstructs bidder preferences and the allocator from only which bidders show up and who wins, with two concrete models and provable mistake bounds. For… | ||
| Random Projections for Probabilistic Inference | Stefano Ermon | 51m |
Combining random parity constraints with variational inference yields a practical project-then-optimize pipeline that converts counting the partition function… | ||
| Approximation Algorithms for Optimization under Uncertainty | Anupam Gupta | 40m |
Stochastic knapsack treats item sizes (and sometimes rewards) as known distributions and compares online policies to the optimal adaptive decision tree… | ||
| Outposts Between Worst- and Average Case Analysis: A Case Study in Auction Design | Tim Roughgarden | 48m |
Worst-case analysis gives no guidance for reserve prices, while Bayesian (average-case) theory (Myerson) yields closed-form optimal auctions and in the iid… | ||
| Semantic Foundations for Probabilistic Programming | Chris Heunen | 49m |
Develops a denotational semantics for an idealized Anglican (a Church fork) that supports continuous distributions, higher-order functions, soft constraints… | ||
| Black-Box Variational Inference for Probabilistic Programs | Hongseok Yang | 38m |
Claims that black‑box variational inference applies to universal probabilistic programs by converting the program into a parameterized approximating program… | ||
| nothing matches | ||