Pith Number

pith:7RGT5VOR

pith:2026:7RGT5VORVERLDTV3ENGI64ZB3Q

not attested not anchored not stored refs resolved

Improved Parallel Algorithms for EF1 Allocations

D Ellis Hershkowitz, Gregory Kehne, Kishen N Gowda, Richard Z Huang

New parallel algorithms compute EF1 allocations in NC for any constant number of agents while cutting depth and work for two agents.

arxiv:2605.16791 v1 · 2026-05-16 · cs.DS · cs.GT

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{7RGT5VORVERLDTV3ENGI64ZB3Q}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

We significantly generalize beyond 3 agents by giving NC algorithms for any constant number of agents. We also give randomized algorithms with depth Õ(m/n) and polynomial work.

C2weakest assumption

The input valuations allow efficient parallel access and comparison operations in the PRAM or similar model without hidden logarithmic overheads that would invalidate the claimed depth bounds (implicit in the parallel algorithm constructions described in the abstract).

C3one line summary

NC algorithms for EF1 with any constant number of agents, O(log m) depth for two agents, and RNC for EFk allocations up to k approximately sqrt(m).

References

55 extracted · 55 resolved · 0 Pith anchors

[1] Fairly Allocating Goods in Parallel , author=

[2] A sublinear parallel algorithm for stable matching , volume =

[3] 2020 , issue_date = 2020

[4] Best of both worlds: Ex-ante and ex-post fairness in resource allocation , author=

[5] and Fineman, Jeremy T

Receipt and verification

First computed	2026-05-20T00:03:22.257767Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

fc4d3ed5d1a922b1cebb234c8f7321dc2c9f0a96909947da40daf2f0d3f34bd4

Aliases

arxiv: 2605.16791 · arxiv_version: 2605.16791v1 · doi: 10.48550/arxiv.2605.16791 · pith_short_12: 7RGT5VORVERL · pith_short_16: 7RGT5VORVERLDTV3 · pith_short_8: 7RGT5VOR

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/7RGT5VORVERLDTV3ENGI64ZB3Q \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: fc4d3ed5d1a922b1cebb234c8f7321dc2c9f0a96909947da40daf2f0d3f34bd4

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "3c322c05cd5fc5f7d61fd267a441b864f6a35771f111b798883fba4f14652cdb",
    "cross_cats_sorted": [
      "cs.GT"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.DS",
    "submitted_at": "2026-05-16T03:50:42Z",
    "title_canon_sha256": "d9cd7e20748abb22f550005a8fb7e3b33e1d038052a71dcd9f69cf588267b95d"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.16791",
    "kind": "arxiv",
    "version": 1
  }
}