Monotone Circuits for Connectivity Require Super-Logarithmic Depth

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

Cited in

(83)

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

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)