Shifting Graphs and Their Applications
From MaRDI portal
Publication:4102736
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
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