Boolean Functions whose Monotone Complexity is of Size n2/log n

No abstract is available for this paper.

• Publication year

  1981

• Venue

  Theoretical Computer Science

• Publication date

  1981-03-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0304-3975(89)90084-4
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On Another Boolean Matrix

  1980cited by this paper
• A new lower bound on the monotone network complexity of Boolean sums

  1980cited by this paper
• Switching Functions Whose Monotone Complexity is Nearly Quadratic

  1979cited by this paper
• The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting, and Merging

  1979cited by this paper
• Shifting Graphs and Their Applications

  1976cited by this paper
• Complexity of monotone networks for computing conjunctions

  1976cited by this paper
• Complexity of Monotone Networks for Boolean Matrix Product

  1974cited by this paper
• The power of negative thinking in multiplying Boolean matrices

  1974cited by this paper
• Combinational Complexity of Some Monotone Functions

  1974cited by this paper
• An Improved Lower Bound for Sorting Networks

  1972cited by this paper

• On the approximation method and the P versus NP problem

  2024cites this paper
• Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution

  2017cites this paper
• On the complexity of hazard-free circuits

  2017cites this paper
• On the Complexity of Hazard-free Circuits

  2017cites this paper
• Circuit Complexity

  2010cites this paper
• On Negations in Boolean Networks

  2009cites this paper
• Growth processes on formulas and reversible circuits

  2003cites this paper
• Monotone Boolean functions

  2003cites this paper
• about the Internet and Networking : 2010 – 2019

  2003cites this paper
• The Complexity of Computing the k-ary Composition of a Binary Associative Operator

  1996cites this paper
• A Super-Logarithmic Lower Bound for Hypercubic Sorting Networks

  1994cites this paper
• The Complexity of Finite Functions

  1991cites this paper
• On Monotone Simulations of Nonmonotone Networks

  1989cites this paper
• Entropy of Contact Circuits and Lower Bounds on Their Complexity

  1988cites this paper
• Constructive Universal Algebra: An Introduction

  1987cites this paper
• The monotone circuit complexity of boolean functions

  1987cites this paper
• More on the Complexity of Slice Functions

  1986cites this paper
• The Complexity of Central Slice Functions

  1986cites this paper
• Lower bounds on monotone complexity of the logical permanent

  1985cites this paper
• Planar Circuits Have Short Specifications

  1985cites this paper
• An Omega(n-4/3) Lower Bound on the Monotone Network Complexity of the n-th Degree Convolution

  1985cites this paper
• On the Complexity of Slice Functions

  1984cites this paper
• A 2.5n lower bound on the monotone network complexity of T3n

  1984cites this paper
• An n^3/2 Lower Bound on the Monotone Network Complexity of the Boolean Convolution

  1984cites this paper
• Exponential lower bounds for restricted monotone circuits

  1983cites this paper
• Proving lower bounds of the monotone complexity of Boolean functions

  1983cites this paper
• Relating Monotone Formula Size and Monotone Depth of Boolean Functions

  1983cites this paper