Monotone Circuits for Connectivity Require Super-Logarithmic Depth

DOI10.1137/0403021zbMATH Open0695.94021OpenAlexW2049016755MaRDI QIDQ3472058FDOQ3472058

Authors: A. Wigderson, Mauricio Karchmer 

Publication date: 1990

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0403021

Recommendations

• Monotone Circuits for Connectivity Have Depth (log n)^2-o(1)
• A simple lower bound for monotone clique using a communication game
• scientific article; zbMATH DE number 1263233
• Monotone circuits for matching require linear depth
• Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes

zbMATH Keywords

communication complexitygraph connectivityundirected graphcircuit complexitymonotone circuitcomplexity of Boolean functions

Mathematics Subject Classification ID

Connectivity (05C40) Boolean functions (06E30)

Cited In (83)

• On the optimality of Bellman-Ford-Moore shortest path algorithm
• On the power of circuits with gates of low \(L_{1}\) norms.
• New bounds on the half-duplex communication complexity
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• How Do Read-Once Formulae Shrink?
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Lower bounds for tropical circuits and dynamic programs
• Partition arguments in multiparty communication complexity
• Circuit complexity meets ontology-based data access
• On Linear Secret Sharing for Connectivity in Directed Graphs
• Linear algebraic methods in communication complexity
• Smallest formulas for the parity of \(2^k\) variables are essentially unique
• Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
• Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
• Proof complexity of monotone branching programs
• Results on communication complexity classes
• A stronger LP bound for formula size lower bounds via clique constraints
• The complexity of graph connectivity
• Monotone circuits for matching require linear depth
• On the mystery of negations in circuits: structure vs power
• The direct sum of universal relations
• Simulation theorems via pseudo-random properties
• Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes
• On the power of small-depth threshold circuits
• Communication complexity and combinatorial lattice theory
• Monotone separation of logarithmic space from logarithmic depth
• On convex complexity measures
• Prediction from partial information and hindsight, with application to circuit lower bounds
• Monotone circuit lower bounds from resolution
• A note on monotone complexity and the rank of matrices
• A feasible interpolation for random resolution
• Natural proofs
• Clique problem, cutting plane proofs and communication complexity
• Choosing, agreeing, and eliminating in communication complexity
• Improved composition theorems for functions and relations
• Directed monotone contact networks for threshold functions
• Lower bounds for Boolean circuits of bounded negation width
• Formulas versus Circuits for Small Distance Connectivity
• A simple lower bound for monotone clique using a communication game
• On derandomized composition of Boolean functions
• Top-down lower bounds for depth-three circuits
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Toward better depth lower bounds: two results on the multiplexor relation
• A note on monotone real circuits
• Smallest Formulas for Parity of 2 k Variables Are Essentially Unique
• Strengthening convex relaxations of 0/1-sets using Boolean formulas
• Depth lower bounds for monotone semi-unbounded fan-in circuits.
• Extension complexity of independent set polytopes
• Optimal bounds for the predecessor problem and related problems
• Time-space tradeoffs for branching programs
• Trade-offs between communication and space
• Constructing depth-optimum circuits for adders and \textsc{And}-\textsc{Or} paths
• Resolution over linear equations and multilinear proofs
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• On data structures and asymmetric communication complexity
• Adventures in monotone complexity and TFNP
• On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
• The choice and agreement problems of a random function
• Dag-like communication and its applications
• New bounds for energy complexity of Boolean functions
• Limitations of incremental dynamic programming
• Lifting Theorems for Equality
• Communication lower bounds via critical block sensitivity
• A super-quadratic lower bound for depth four arithmetic circuits
• Title not available (Why is that?)
• Complexity of the realization of a linear Boolean function in the class of \(\pi\)-schemes
• On the depth of a multiplexer function with a small number of select lines
• Title not available (Why is that?)
• Number of variables is equivalent to space
• Communication complexity meets cellular automata: necessary conditions for intrinsic universality
• On negation complexity of injections, surjections and collision-resistance in cryptography
• Minimum vertex cover, distributed decision-making, and communication complexity
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Sufficient conditions for the local repetition-freeness of minimal \(\pi\)-schemes realizing linear Boolean functions
• Small extended formulation for knapsack cover inequalities from monotone circuits
• Lower bounds for approximating graph parameters via communication complexity
• Breaking the rectangle bound barrier against formula size lower bounds
• Average circuit depth and average communication complexity
• Exploring the limits of subadditive approaches: parallels between optimization and complexity theory
• Bounds in ontology-based data access via circuit complexity
• On the perfectness of minimal regular partitions of the edge set of the \(n\)-dimensional cube
• On the meaning of works by V. M. Khrapchenko

This page was built for publication: Monotone Circuits for Connectivity Require Super-Logarithmic Depth

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