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

(95)

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

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)