A sorting network in bounded arithmetic
From MaRDI portal
Publication:638498
DOI10.1016/j.apal.2010.10.002zbMath1257.03087OpenAlexW2103489902MaRDI QIDQ638498
Publication date: 12 September 2011
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.apal.2010.10.002
Related Items
Proofs with monotone cuts ⋮ Expander Construction in VNC1 ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ On theories of bounded arithmetic for \(\mathrm{NC}^1\) ⋮ Proof complexity of monotone branching programs
Cites Work
- Improved sorting networks with O(log N) depth
- On theories of bounded arithmetic for \(\mathrm{NC}^1\)
- Sorting in \(c \log n\) parallel steps
- The monotone circuit complexity of Boolean functions
- On uniform circuit complexity
- Monotone simulations of non-monotone proofs.
- Short monotone formulae for the majority function
- On the Number of Stable States in a NOR Network
- Unnamed Item
- Unnamed Item
