Ian D'Ambrosio

Always-Correct Succinct Dynamic Fusion Nodes Are Impossible: A Cell-Probe Lower Bound in the Small-Set, Large-Universe Regime

This record contains the paper and reproducibility package for a cell-probe lower bound that rules out always-correct succinct constant-time dynamic fusion nodes in the fixed-layout packed-memory model. The package includes the full Lean 4 formalization for deterministic and fres...

Adaptive Perturbation Design for Causal Edge Recovery: Block-Graph Guarantees and Unbounded Marginal Inflation

We study adaptive intervention design for orienting causal directed acyclic graphs within an observational Markov equivalence class under a uniform prior and atomic perfect interventions. We prove that the compelled-edge reward is adaptively monotone and adaptively submodular whe...

A Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving

Huang, Lou, and Xiao introduced Dynamic Mixture-of-Experts Serving and gave an O(sqrt(log k))-competitive randomized algorithm for the integral primal, leaving the primal order open. This preprint proves that the randomized primal competitive ratio is Theta(1) for arbitrary numbe...