asymptotic-wcgbp

Asymptotic-WCGBP Artifact

This repository contains the artifact code for high-precision asymptotic experiments on worst-case generalized birthday problem (GBP) instances. It also includes mpoptimize, a small mpmath-backed constrained optimization package used by the artifact scripts.

The repository is intended to support two reproducible workflows:

• uv workflow for building, locking, running, and testing the whole project.
• requirements.txt workflow for recreating the currently verified local environment exactly.

Disclaimer: We used Codex + GPT-5.5 to develop the mpoptimize package, sampler scripts, and plotting scripts. We manually wrote the (regular) ISD models based on Regular-ISD/asymptotics.ipynb and verified the correctness of the generated code. Comprehensive tests were added to ensure the correctness of the numeric numerical optimization (see tests and example).

Contents

• src/mpoptimize/: high-precision minimize(...) implementation with SLSQP-like and COBYLA-like methods.
• mp_*_isd.py, mp_*_sampler.py, *_points.py: asymptotic ISD models and JSON data generation scripts.
• json/: precomputed artifact data used by the plotting scripts.
• plot_*.py: plotting scripts for the figures in fig/ and comparison figures generated from the JSON data.
• tests/: smoke, regression, and high-precision tests for mpoptimize.

Installation

• Python >=3.10,<3.13 (the repository pins SciPy 1.11.4; Python 3.13+ may force a source build instead of using wheels)
• uv for the preferred artifact workflow

The pinned package versions used by the current working environment are listed in requirements.txt.

Installation With uv

Create or update the project environment:

uv sync --all-extras

Run commands inside the managed environment:

uv run pytest
uv run plot-wc-rgbp
uv run plot-wc-lgbp
uv run plot-sdp-paras
uv run plot-wc-gbp
uv run plot-optimal-wcgbp

Build the local package:

uv build

Install the repository as an editable local package:

uv pip install -e ".[artifact,test]"

After editable installation, the console commands above are available in the active environment. Run plotting commands from the repository root so the scripts can use the bundled json/ data and write figures under fig/.

Installation With requirements.txt

For a plain virtual environment without uv:

python -m venv .venv
source .venv/bin/activate
python -m pip install --upgrade pip
python -m pip install -r requirements.txt
python -m pip install -e ".[test]"

This installs the same direct and transitive runtime versions as the currently verified local environment:

• mpmath==1.3.0
• matplotlib==3.8.0
• numpy==1.26.3
• scipy==1.11.4

Reproducing Results

The repository includes precomputed JSON files under json/. To regenerate a small scan manually:

# small scans for regular and loose GBP points
uv run regular-rgbp-points --algorithm enum --start 0.01 --end 0.10 --step 0.01
uv run standard-lgbp-points --algorithm enum --start 0.01 --end 0.10 --step 0.01

Full scans can be expensive because each point may solve a high-precision constrained optimization problem. The plotting scripts use the latest matching JSON file by filename prefix. To regenerate the full JSON data set for every registered algorithm:

#!/usr/bin/env bash
set -euo pipefail

# Full regular-GBP scans: c = 0.01, 0.02, ..., 1.00
for alg in perm enum rep rep_mo; do
  uv run regular-rgbp-points --algorithm "$alg" --start 0.01 --end 1.00 --step 0.01
done

# Full loose-GBP scans: c = 0.01, 0.02, ..., 0.50
for alg in perm enum rep rep_mo; do
  uv run standard-lgbp-points --algorithm "$alg" --start 0.01 --end 0.50 --step 0.01
done

Plotting

Generate the regular and loose GBP complexity plots:

uv run plot-wc-rgbp
uv run plot-wc-lgbp

Generate the side-by-side and optimal comparison plots:

uv run plot-wc-gbp
uv run plot-optimal-wcgbp

By default these commands write fig/complexity_gbp.pdf and fig/optimal_wcgbp.pdf, respectively.

Generate the worst-case parameter plots:

uv run plot-sdp-paras

Testing

Run the test suite with:

uv run pytest

or, in a manually managed environment:

pytest

Notes

mpoptimize is a pure Python high-precision baseline. It avoids implicit float64 downcasting in the core optimization loops, but it is not intended to be a feature-complete replacement for SciPy's optimizers.