Shifting Graphs and Their Applications

DOI10.1145/321958.321962zbMath0335.68032OpenAlexW2035081987MaRDI QIDQ4102736

Leslie G. Valiant, Nicholas J. Pippenger

Publication date: 1976

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321958.321962

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Related Items (17)

A lower bound on strictly non-blocking networks ⋮ Efficient monotone circuits for threshold functions ⋮ Time-space tradeoffs for computing functions, using connectivity properties of their circuits ⋮ Negation can be exponentially powerful ⋮ The parallel reversible pebbling game: analyzing the post-quantum security of iMHFs ⋮ Boolean functions whose monotone complexity is of size \(n^ 2\) / log n ⋮ Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution ⋮ Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ On shifting networks ⋮ Reductions for monotone Boolean circuits ⋮ Rotator design ⋮ Unnamed Item ⋮ On Negations in Boolean Networks ⋮ Size-space tradeoffs for oblivious computations ⋮ An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution ⋮ Rearrangeable Networks with Limited Depth ⋮ A New Lower Bound for the Number of Switches in Rearrangeable Networks

This page was built for publication: Shifting Graphs and Their Applications