3 citations · 11 across the 17 of their papers we have counts for
21 papers
Proxy-Based Approximation of Shapley and Banzhaf Interactions
Santo M. A. R. Thies, Hubert Baniecki, R. Teal Witter +3
Shapley and Banzhaf interactions capture the complex dynamics inherent in modern machine learning applications. However, current estimators for these higher-order interactions trad…
Exactly Computing do-Shapley Values
R. Teal Witter, Álvaro Parafita, Tomas Garriga +4
Structural Causal Models (SCM) are a powerful framework for describing complicated dynamics across the natural sciences. A particularly elegant way of interpreting SCMs is do-Shapl…
An Odd Estimator for Shapley Values
Fabian Fumagalli, Landon Butler, Justin Singh Kang +2
The Shapley value is a ubiquitous framework for attribution in machine learning, encompassing feature importance, data valuation, and causal inference. However, its exact computati…
PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression
Fabian Fumagalli, R. Teal Witter, Christopher Musco
Shapley values have emerged as a central game-theoretic tool in explainable AI (XAI). However, computing Shapley values exactly requires game evaluations for a model with …
SimKey: A Semantically Aware Key Module for Watermarking Language Models
Shingo Kodama, Haya Diwan, Lucas Rosenblatt +2
The rapid spread of text generated by large language models (LLMs) makes it increasingly difficult to distinguish authentic human writing from machine output. Watermarking offers a…
Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values
R. Teal Witter, Yurong Liu, Christopher Musco
With origins in game theory, probabilistic values like Shapley values, Banzhaf values, and semi-values have emerged as a central tool in explainable AI. They are used for feature a…
SEAL: Semantic Aware Image Watermarking
Kasra Arabi, R. Teal Witter, Chinmay Hegde +1
Generative models have rapidly evolved to generate realistic outputs. However, their synthetic outputs increasingly challenge the clear distinction between natural and AI-generated…
Hidden in the Noise: Two-Stage Robust Watermarking for Images
Kasra Arabi, Benjamin Feuer, R. Teal Witter +2
As the quality of image generators continues to improve, deepfakes become a topic of considerable societal debate. Image watermarking allows responsible model owners to detect and…
FairlyUncertain: A Comprehensive Benchmark of Uncertainty in Algorithmic Fairness
Lucas Rosenblatt, R. Teal Witter
Fair predictive algorithms hinge on both equality and trust, yet inherent uncertainty in real-world data challenges our ability to make consistent, fair, and calibrated decisions.…
Kernel Banzhaf: A Fast and Robust Estimator for Banzhaf Values
Yurong Liu, R. Teal Witter, Flip Korn +4
Banzhaf values provide a popular, interpretable alternative to the widely-used Shapley values for quantifying the importance of features in machine learning models. Like Shapley va…
Provably Accurate Shapley Value Estimation via Leverage Score Sampling
Christopher Musco, R. Teal Witter
Originally introduced in game theory, Shapley values have emerged as a central tool in explainable machine learning, where they are used to attribute model predictions to specific…
Benchmarking Estimators for Natural Experiments: A Novel Dataset and a Doubly Robust Algorithm
R. Teal Witter, Christopher Musco
Estimating the effect of treatments from natural experiments, where treatments are pre-assigned, is an important and well-studied problem. We introduce a novel natural experiment d…
Minimizing Cost Rather Than Maximizing Reward in Restless Multi-Armed Bandits
R. Teal Witter, Lisa Hellerstein
Restless Multi-Armed Bandits (RMABs) offer a powerful framework for solving resource constrained maximization problems. However, the formulation can be inappropriate for settings w…
I Open at the Close: A Deep Reinforcement Learning Evaluation of Open Streets Initiatives
R. Teal Witter, Lucas Rosenblatt
The open streets initiative "opens" streets to pedestrians and bicyclists by closing them to cars and trucks. The initiative, adopted by many cities across North America, increases…
Robust and Space-Efficient Dual Adversary Quantum Query Algorithms
Michael Czekanski, Shelby Kimmel, R. Teal Witter
The general adversary dual is a powerful tool in quantum computing because it gives a query-optimal bounded-error quantum algorithm for deciding any Boolean function. Unfortunately…
A Local Search Algorithm for the Min-Sum Submodular Cover Problem
Lisa Hellerstein, Thomas Lidbetter, R. Teal Witter
We consider the problem of solving the Min-Sum Submodular Cover problem using local search. The Min-Sum Submodular Cover problem generalizes the NP-complete Min-Sum Set Cover probl…
Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem
Lisa Hellerstein, Devorah Kletenik, Naifeng Liu +1
We consider the Stochastic Boolean Function Evaluation (SBFE) problem where the task is to efficiently evaluate a known Boolean function on an unknown bit string of length…
Counterfactual Fairness Is Basically Demographic Parity
Lucas Rosenblatt, R. Teal Witter
Making fair decisions is crucial to ethically implementing machine learning algorithms in social settings. In this work, we consider the celebrated definition of counterfactual fai…
Backgammon is Hard
R. Teal Witter
We study the computational complexity of the popular board game backgammon. We show that deciding whether a player can win from a given board configuration is NP-Hard, PSPACE-Hard,…
A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs
Shelby Kimmel, R. Teal Witter
We design quantum algorithms for maximum matching. Working in the query model, in both adjacency matrix and adjacency list settings, we improve on the best known algorithms for gen…
Applications of the quantum algorithm for st-connectivity
Kai DeLorenzo, Shelby Kimmel, R. Teal Witter
We present quantum algorithms for various problems related to graph connectivity. We give simple and query-optimal algorithms for cycle detection and odd-length cycle detection (bi…