Formalizing Randomized Matching Algorithms
From MaRDI portal
Publication:2904622
DOI10.2168/LMCS-8(3:5)2012zbMath1256.03061arXiv1103.5215OpenAlexW1980738047MaRDI QIDQ2904622
Dai Tri Man Lê, Stephen A. Cook
Publication date: 15 August 2012
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1103.5215
computational complexitybounded arithmeticrandomized algorithmsprobabilistic reasoningpolynomial identity testingweak pigeonhole principle
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Randomized algorithms (68W20) Complexity of proofs (03F20)
Related Items (2)
Unprovability of strong complexity lower bounds in bounded arithmetic ⋮ Indistinguishability obfuscation, range avoidance, and bounded arithmetic
This page was built for publication: Formalizing Randomized Matching Algorithms
