Paper Citation Record · LEDGER

Lower Bounds for Non-adaptive Local Computation Algorithms

As of 17 August 2026, this Paper Citation Record lists 34 of 34 outbound references and 0 inbound Pith citation observations for arXiv:2505.00915.

A citation records a reference. It does not transfer a finding from one paper to another.

pith.paper-citation-record.v1
2505.00915 v1

Coverage vector

measured 34 of 34 reference resolution

Typed states for the displayed outbound observations.

Source: paper_references, paper_reference_links, observed 2026-08-16T04:47:55.501385Z

measured 34 of 34 standing notices

One-hop event checks from named stored sources.

Source: scholarly_work_events, retraction_status_cache, observed 2026-08-17T06:30:58.91139+00:00

measured 0 of 0 inbound itemization

Pith citing papers itemized under the disclosed page cap.

Source: paper_references, paper_reference_links

measured 0 of 1 external citation measurements

A source-named dated measurement, never combined with another source.

Source: cited_works

Reference resolution

34 of 34 outbound references displayed

verified exact3
verified fuzzy15
unresolved15
parse uncertain0
malformed identifier1
metadata mismatch0

External citation measurements

No source-named external measurement is stored.

Outbound references

Observation 4ee5004d-5c2e-4e60-aaf7-c2ea29aa01bb · outbound

This paper cites Sp ace-Eﬃcient Local Computation Algorithms.

Lower Bounds for Non-adaptive Local Computation Algorithms Sp ace-Eﬃcient Local Computation Algorithms

Reference 1

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:56.140269Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation a5e50638-68d1-40e6-98df-3f740bdb9c21 · outbound

This paper cites The stochast ic matching problem with (very) few queries.

Lower Bounds for Non-adaptive Local Computation Algorithms The stochast ic matching problem with (very) few queries

Reference 2

Resolution: unresolved; no resolver link, observed 2026-08-16T04:47:55.389862Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation c258ea65-983a-4302-842e-430014f4703e · outbound

This paper cites Lower bounds for maximal matchings and maximal ind ependent sets.

Lower Bounds for Non-adaptive Local Computation Algorithms Lower bounds for maximal matchings and maximal ind ependent sets

Reference 3

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:56.130241Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation add5588d-4580-447f-850d-73ca01095999 · outbound

This paper cites A distributed (2 + ε)- approximation for vertex cover in o(log ∆ / ε log log ∆) rounds.

Lower Bounds for Non-adaptive Local Computation Algorithms A distributed (2 + ε)- approximation for vertex cover in o(log ∆ / ε log log ∆) rounds

Reference 4

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:56.119983Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation 53048822-2dbb-4388-ac21-639929fa6a84 · outbound

This paper cites The locality of dis- tributed symmetry breaking.

Lower Bounds for Non-adaptive Local Computation Algorithms The locality of dis- tributed symmetry breaking

Reference 5

Resolution: unresolved; no resolver link, observed 2026-08-16T04:47:55.405441Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 0d220b86-bd0a-4028-9dc8-349fa53b3a06 · outbound

This paper cites Time-Optimal Sublinear Algorithms f or Matching and Vertex Cover.

Lower Bounds for Non-adaptive Local Computation Algorithms Time-Optimal Sublinear Algorithms f or Matching and Vertex Cover

Reference 6

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:56.109106Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation f0785b92-a57b-4e15-8158-2f75dddcf744 · outbound

This paper cites Stochastic matching with few queries: (1- ε) approximation.

Lower Bounds for Non-adaptive Local Computation Algorithms Stochastic matching with few queries: (1- ε) approximation

Reference 7

Resolution: unresolved; no resolver link, observed 2026-08-16T04:47:55.412777Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 7b5c6de3-bbc6-43ae-b1d8-44ea5edb5e3d · outbound

This paper cites Sublinear time algorithms and complexity of approximate maximum matching.

Lower Bounds for Non-adaptive Local Computation Algorithms Sublinear time algorithms and complexity of approximate maximum matching

Reference 8

Resolution: verified exact; doi, observed 2026-08-16T04:47:55.587731Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation 40639ecd-8886-4e7b-91dc-a60fc39dec09 · outbound

This paper cites Local computation algorithms for maximum matching: New lower bounds.

Lower Bounds for Non-adaptive Local Computation Algorithms Local computation algorithms for maximum matching: New lower bounds

Reference 9

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:56.099412Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation fafec30a-a392-4394-aacc-73442482ffbd · outbound

This paper cites Approximating maximum matching requires almost quadratic time.

Lower Bounds for Non-adaptive Local Computation Algorithms Approximating maximum matching requires almost quadratic time

Reference 10

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:56.088905Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation 14994c94-ae2b-4c00-8048-c82d00b5b66b · outbound

This paper cites Canonne and Tom Gur.

Lower Bounds for Non-adaptive Local Computation Algorithms Canonne and Tom Gur

Reference 11

Resolution: verified exact; doi, observed 2026-08-16T04:47:55.575443Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation 60b9a7f1-1b18-4bd4-b894-e791e0f46cba · outbound

This paper cites Servedio, Li-Yang Tan, and Erik Wainga rten.

Lower Bounds for Non-adaptive Local Computation Algorithms Servedio, Li-Yang Tan, and Erik Wainga rten

Reference 12

Resolution: malformed identifier; no resolver link, observed 2026-08-16T04:47:55.430822Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 2f48150d-ac1d-41a8-b3d9-8ae03406b174 · outbound

This paper cites Served io, and Erik Waingarten.

Lower Bounds for Non-adaptive Local Computation Algorithms Served io, and Erik Waingarten

Reference 13

Resolution: verified exact; doi, observed 2026-08-16T04:47:55.558070Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation 1bc69e41-caa6-4aa1-9916-b2c3ee5525a3 · outbound

This paper cites Monotonicity testing over general poset do mains.

Lower Bounds for Non-adaptive Local Computation Algorithms Monotonicity testing over general poset do mains

Reference 14

Resolution: unresolved; no resolver link, observed 2026-08-16T04:47:55.437847Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 0f8e9b9b-c137-4c10-ab07-a82c9be277db · outbound

This paper cites Local computation of maximal independe nt set.

Lower Bounds for Non-adaptive Local Computation Algorithms Local computation of maximal independe nt set

Reference 15

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:56.078163Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation dc230fb9-a28d-4780-beea-212f4c970ced · outbound

This paper cites Sparsifying distributed algorithms with ramiﬁcations in massively parallel computation and centralized local comp utation.

Lower Bounds for Non-adaptive Local Computation Algorithms Sparsifying distributed algorithms with ramiﬁcations in massively parallel computation and centralized local comp utation

Reference 16

Resolution: unresolved; no resolver link, observed 2026-08-16T04:47:55.444436Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 62f82284-7263-40c7-93e4-3fa1896913a2 · outbound

This paper cites Th e power of adaptivity in quan- tum query algorithms.

Lower Bounds for Non-adaptive Local Computation Algorithms Th e power of adaptivity in quan- tum query algorithms

Reference 17

Resolution: unresolved; no resolver link, observed 2026-08-16T04:47:55.447791Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 713b1651-f985-4a01-9442-9c9fe1aa2750 · outbound

This paper cites Three theorems regar ding testing graph properties.

Lower Bounds for Non-adaptive Local Computation Algorithms Three theorems regar ding testing graph properties

Reference 18

Resolution: unresolved; no resolver link, observed 2026-08-16T04:47:55.451244Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 6d335817-73e9-4765-a176-bb83c5475080 · outbound

This paper cites On the beneﬁts of adaptivity in p roperty testing of dense graphs.

Lower Bounds for Non-adaptive Local Computation Algorithms On the beneﬁts of adaptivity in p roperty testing of dense graphs

Reference 19

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:56.066562Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation 006c9c8a-e631-4130-a58f-2c4fa6bc971c · outbound

This paper cites an unresolved cited work.

Lower Bounds for Non-adaptive Local Computation Algorithms Unresolved cited work

Reference 20

Resolution: unresolved; no resolver link, observed 2026-08-16T04:47:55.457960Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation bd5d7661-febb-4f80-b0e0-90bafc077758 · outbound

This paper cites Space Eﬃcient Approximation to Maximum Matching Size from Uniform Edge Sa mples.

Lower Bounds for Non-adaptive Local Computation Algorithms Space Eﬃcient Approximation to Maximum Matching Size from Uniform Edge Sa mples

Reference 21

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:56.053951Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation df4ef64a-c78a-4707-91cd-8926f2203fec · outbound

This paper cites Karloﬀ, Siddharth Suri, and Sergei Vassilvits kii.

Lower Bounds for Non-adaptive Local Computation Algorithms Karloﬀ, Siddharth Suri, and Sergei Vassilvits kii

Reference 22

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:56.042229Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation 5c680696-fbb0-46d0-b0f8-3d0f15a4dfdc · outbound

This paper cites Local computation: Lower and upper bounds.

Lower Bounds for Non-adaptive Local Computation Algorithms Local computation: Lower and upper bounds

Reference 23

Resolution: unresolved; no resolver link, observed 2026-08-16T04:47:55.467746Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 104640df-1418-4657-817b-28762bf75453 · outbound

This paper cites Prop erly learning monotone functions via local correction.

Lower Bounds for Non-adaptive Local Computation Algorithms Prop erly learning monotone functions via local correction

Reference 24

Resolution: unresolved; no resolver link, observed 2026-08-16T04:47:55.470977Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation cb707897-cd2b-4cc9-a4d0-2bd30de4c19a · outbound

This paper cites Locality in distributed graph algorith ms.

Lower Bounds for Non-adaptive Local Computation Algorithms Locality in distributed graph algorith ms

Reference 25

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:56.030226Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation 53ed5b4c-b653-4202-9b9c-bebe8450c073 · outbound

This paper cites Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space.

Lower Bounds for Non-adaptive Local Computation Algorithms Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space

Reference 26

Resolution: unresolved; no resolver link, observed 2026-08-16T04:47:55.481437Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation e7f95f39-15d3-4fa7-a39d-6c5a7d268430 · outbound

This paper cites Approximating the Minimum V ertex Cover in Sublinear Time and a Connection to Distributed Algorithms.

Lower Bounds for Non-adaptive Local Computation Algorithms Approximating the Minimum V ertex Cover in Sublinear Time and a Connection to Distributed Algorithms

Reference 27

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:56.018962Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation 4fd9984c-8697-48e2-b288-ff34045fd6ba · outbound

This paper cites an unresolved cited work.

Lower Bounds for Non-adaptive Local Computation Algorithms Unresolved cited work

Reference 28

Resolution: unresolved; raw_fallback, observed 2026-08-16T04:47:56.007322Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation c715fb33-7ca3-451d-baac-a29de409fd87 · outbound

This paper cites F ast local computation algorithms.

Lower Bounds for Non-adaptive Local Computation Algorithms F ast local computation algorithms

Reference 29

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:55.995651Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation 421e311a-9998-472d-a3f7-3daded1a3f19 · outbound

This paper cites An impro ved constant-time approximation algorithm for maximum matchings.

Lower Bounds for Non-adaptive Local Computation Algorithms An impro ved constant-time approximation algorithm for maximum matchings

Reference 30

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:55.984956Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation 165933a9-502d-47ec-82d8-d7f66ff31bfd · outbound

This paper cites an unresolved cited work.

Lower Bounds for Non-adaptive Local Computation Algorithms Unresolved cited work

Reference 33

Resolution: unresolved; raw_fallback, observed 2026-08-16T04:47:55.974174Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation d5280a5e-a511-4783-bdc3-4941b819d0ed · outbound

This paper cites Then, for every i ∈ {0, 1,.

Lower Bounds for Non-adaptive Local Computation Algorithms Then, for every i ∈ {0, 1,

Reference 34

Resolution: verified fuzzy; raw_fallback, observed 2026-08-16T04:47:55.963137Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-17T06:30:58.91139+00:00.

Observation 9c8e69f6-903f-483c-a858-aecb28509e87 · outbound

This paper cites an unresolved cited work.

Lower Bounds for Non-adaptive Local Computation Algorithms Unresolved cited work

Reference 1992

Resolution: unresolved; no resolver link, observed 2026-08-16T04:47:55.477735Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 4e96c1b3-fe34-49fb-a2bf-aacfcd5d9ffe · outbound

This paper cites an unresolved cited work.

Lower Bounds for Non-adaptive Local Computation Algorithms Unresolved cited work

Reference 2017

Resolution: unresolved; no resolver link, observed 2026-08-16T04:47:55.401599Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Pith citing papers

No inbound Pith citation observations are available.