Monotone Circuits for Connectivity Require Super-Logarithmic Depth
From MaRDI portal
Publication:3472058
DOI10.1137/0403021zbMath0695.94021OpenAlexW2049016755MaRDI QIDQ3472058
Avi 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
circuit complexitygraph connectivitycommunication complexityundirected graphmonotone circuitcomplexity of Boolean functions
Related Items
On the optimality of Bellman-Ford-Moore shortest path algorithm, Directed monotone contact networks for threshold functions, Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity, Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes, New bounds on the half-duplex communication complexity, Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes, On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography, Applications of matrix methods to the theory of lower bounds in computational complexity, Sufficient conditions for the local repetition-freeness of minimal π-schemes realizing linear Boolean functions, Communication Lower Bounds via Critical Block Sensitivity, Formulas versus Circuits for Small Distance Connectivity, Top-down lower bounds for depth-three circuits, Complexity of the Realization of a Linear Boolean Function in the Class of π-Schemes, Circuit Complexity Meets Ontology-Based Data Access, Dag-like communication and its applications, Super-logarithmic depth lower bounds via the direct sum in communication complexity, On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube, Bounds in ontology-based data access via circuit complexity, The complexity of graph connectivity, On the power of circuits with gates of low \(L_{1}\) norms., Lower bounds for Boolean circuits of bounded negation width, On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions, A note on monotone real circuits, Communication complexity meets cellular automata: necessary conditions for intrinsic universality, Average circuit depth and average communication complexity, How Do Read-Once Formulae Shrink?, Linear algebraic methods in communication complexity, Smallest Formulas for Parity of 2 k Variables Are Essentially Unique, Minimum vertex cover, distributed decision-making, and communication complexity, Unnamed Item, A stronger LP bound for formula size lower bounds via clique constraints, Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation, Unnamed Item, Unnamed Item, Extension Complexity of Independent Set Polytopes, The choice and agreement problems of a random function, Clique problem, cutting plane proofs and communication complexity, Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory, On Linear Secret Sharing for Connectivity in Directed Graphs, Lower bounds for tropical circuits and dynamic programs, Strengthening convex relaxations of 0/1-sets using Boolean formulas, ON THE MEANING OF WORKS BY V. M. KHRAPCHENKO, Results on communication complexity classes, Resolution over linear equations and multilinear proofs, Limitations of incremental dynamic programming, The direct sum of universal relations, On the power of small-depth threshold circuits, Trade-offs between communication and space, Number of variables is equivalent to space, BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS, On convex complexity measures, Partition arguments in multiparty communication complexity, Smallest formulas for the parity of \(2^k\) variables are essentially unique, Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits, Natural proofs, On the mystery of negations in circuits: structure vs power, Unnamed Item, Simulation theorems via pseudo-random properties, On derandomized composition of Boolean functions, New bounds for energy complexity of Boolean functions, Optimal Lower Bounds on Regular Expression Size Using Communication Complexity, Choosing, agreeing, and eliminating in communication complexity, A note on monotone complexity and the rank of matrices, Adventures in monotone complexity and TFNP, Lifting Theorems for Equality, A super-quadratic lower bound for depth four arithmetic circuits, On data structures and asymmetric communication complexity, Prediction from partial information and hindsight, with application to circuit lower bounds, Non-cancellative Boolean circuits: A generalization of monotone boolean circuits, Constructing depth-optimum circuits for adders and \textsc{And}-\textsc{Or} paths, Unnamed Item, Unnamed Item, Toward better depth lower bounds: two results on the multiplexor relation, Communication complexity and combinatorial lattice theory, Proof complexity of monotone branching programs, A feasible interpolation for random resolution, Time-space tradeoffs for branching programs, Optimal bounds for the predecessor problem and related problems
