sample-complexity

We analyze algorithms to learn Gaussian Bayesian networks with known structure up to a bounded error in total variation distance.

OSRL (Optimal Representation Learning in Multi-Task Bandits) comprises an algorithm that addresses the problem of sample complexity with fixed confidence in Multi-Task Bandit problems. Published at the Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI23)

Paper and verification code: a single-copy lower bound for rank-one nonlinear overlap estimation

Python implementation of algorithms for Best Policy Identification in Markov Decision Processes

Exact retained-qubit frontier for quantum complement sampling, with optimal decoders, converse bounds, source constructions, and dephasing analysis.

Copy and memory limits for quantum reference identification, with finite-query error bounds and sharp saturation of classical preprocessing before an unknown query arrives.

Copy-optimal loop-phase estimation and the coherent-run cost of learning weak quantum overlaps.

Reproduction code for the paper 'Structure, Not Size: The Sample and Parameter Complexity of State Tracking in Selective State-Space Models' (selective PD-SSM / diagonal SSM / GRU state-tracking, MLX).

Optimal dimension-dependent sample cost of short-time Lindblad simulation, with a universal converse and an explicit collective rank-one processor.

Simulation study: copies needed by the six-copy Bell-difference-sampling stabilizer test under dephasing, depolarising and readout noise. Exact statistics, critical noise vs qubits (3-6), threshold ablation, Pauli-shadow baseline, 5 seeds.

Exact flat-rank quantum classification and rank-dependent limits on coherent learning and classical compilation.

Known-state quantum certification under noisy local readout: adaptive sample-complexity bounds, a sharp binary exponent, and fidelity noise thresholds.

Root-fidelity estimation under complete quantum resets, with adaptive converses and a loop-phase application.

An MLP hits a real sample-complexity wall learning sparse parities, with a Fourier-basis progress measure that sees it coming before the loss does

Python utilities to compute a lower bound of the expected sample complexity to identify the best arm in a bandit model

Sharp copy-complexity bounds for noisy quantum purity testing, revealing an exponential advantage of collective measurements over adaptive two-copy strategies.

Optimal outcome counts, polynomial rigidity, and statistical costs of universal entanglement detection using fixed collective quantum measurements.

Copy-complexity separation between quantum conditional-state synthesis and arbitrary classical descriptions, with stabilizer proofs, finite verification, and a Watrous-based learning route.

Optimal local testing of two unknown high-temperature Gibbs states on known bounded-overlap Pauli menus.

Learning hidden Pauli measurements from quantum examples with noisy labels: optimal sample bounds, quantum-memory advantage, and conditional hardness under quantum decision-LPN.