A sorting network in bounded arithmetic

DOI10.1016/J.APAL.2010.10.002MaRDI QIDQ638498zbMATH OpenOpenAlexFDO

Authors Emil Jeřábek

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

zbMATH Keywords

bounded arithmeticproof complexitysorting networkmonotone sequent calculus

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• Expander construction in \(\mathsf{VNC}^1\)
• Expander construction in \(\mathrm{VNC}^1\)
• scientific article; zbMATH DE number 1263220
• Improved sorting networks with O(log N) depth
• On theories of bounded arithmetic for \(\mathrm{NC}^1\)

Cites work

• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 1263189 (Why is no real title available?)
• Improved sorting networks with O(log N) depth
• Monotone simulations of non-monotone proofs.
• On the Number of Stable States in a NOR Network
• On theories of bounded arithmetic for \(\mathrm{NC}^1\)
• On uniform circuit complexity
• Short monotone formulae for the majority function
• Sorting in \(c \log n\) parallel steps
• The monotone circuit complexity of Boolean functions

Cited in

(8)

• Expander construction in \(\mathsf{VNC}^1\)
• Proofs with monotone cuts
• Sorting with Complete Networks of Stacks
• Proof complexity of monotone branching programs
• On theories of bounded arithmetic for \(\mathrm{NC}^1\)
• Bounds on the size of test sets for sorting and related networks
• Expander construction in \(\mathrm{VNC}^1\)
• Topological lower bounds for arithmetic networks

This page was built for publication: A sorting network in bounded arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q638498)