Pages that link to "Item:Q3472058"
From MaRDI portal
The following pages link to Monotone Circuits for Connectivity Require Super-Logarithmic Depth (Q3472058):
Displaying 50 items.
- On the optimality of Bellman-Ford-Moore shortest path algorithm (Q266282) (← links)
- Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes (Q293309) (← links)
- Linear algebraic methods in communication complexity (Q417541) (← links)
- A stronger LP bound for formula size lower bounds via clique constraints (Q428879) (← links)
- Clique problem, cutting plane proofs and communication complexity (Q456115) (← links)
- Lower bounds for tropical circuits and dynamic programs (Q493653) (← links)
- Limitations of incremental dynamic programming (Q517805) (← links)
- Partition arguments in multiparty communication complexity (Q541668) (← links)
- On the power of small-depth threshold circuits (Q685717) (← links)
- Choosing, agreeing, and eliminating in communication complexity (Q744609) (← links)
- Toward better depth lower bounds: two results on the multiplexor relation (Q777911) (← links)
- New bounds on the half-duplex communication complexity (Q831813) (← links)
- Resolution over linear equations and multilinear proofs (Q952492) (← links)
- On convex complexity measures (Q964405) (← links)
- Smallest formulas for the parity of \(2^k\) variables are essentially unique (Q974758) (← links)
- A note on monotone complexity and the rank of matrices (Q1014450) (← links)
- Results on communication complexity classes (Q1190990) (← links)
- Trade-offs between communication and space (Q1201877) (← links)
- On data structures and asymmetric communication complexity (Q1273860) (← links)
- Communication complexity and combinatorial lattice theory (Q1309387) (← links)
- Directed monotone contact networks for threshold functions (Q1327314) (← links)
- On the power of circuits with gates of low \(L_{1}\) norms. (Q1389652) (← links)
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits (Q1566723) (← links)
- Time-space tradeoffs for branching programs (Q1604208) (← links)
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity (Q1616616) (← links)
- A note on monotone real circuits (Q1685020) (← links)
- The choice and agreement problems of a random function (Q1705694) (← links)
- The direct sum of universal relations (Q1751432) (← links)
- Optimal bounds for the predecessor problem and related problems (Q1869935) (← links)
- Top-down lower bounds for depth-three circuits (Q1904663) (← links)
- Super-logarithmic depth lower bounds via the direct sum in communication complexity (Q1918946) (← links)
- On the mystery of negations in circuits: structure vs power (Q2019505) (← links)
- Constructing depth-optimum circuits for adders and \textsc{And}-\textsc{Or} paths (Q2074348) (← links)
- Proof complexity of monotone branching programs (Q2104254) (← links)
- Strengthening convex relaxations of 0/1-sets using Boolean formulas (Q2235155) (← links)
- Simulation theorems via pseudo-random properties (Q2281252) (← links)
- On derandomized composition of Boolean functions (Q2281253) (← links)
- Prediction from partial information and hindsight, with application to circuit lower bounds (Q2311545) (← links)
- Dag-like communication and its applications (Q2399382) (← links)
- Bounds in ontology-based data access via circuit complexity (Q2411040) (← links)
- Applications of matrix methods to the theory of lower bounds in computational complexity (Q2638784) (← links)
- Lower bounds for Boolean circuits of bounded negation width (Q2672949) (← links)
- Number of variables is equivalent to space (Q2758055) (← links)
- Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits (Q2773024) (← links)
- Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation (Q2968148) (← links)
- A feasible interpolation for random resolution (Q2980967) (← links)
- On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography (Q3179494) (← links)
- Sufficient conditions for the local repetition-freeness of minimal π-schemes realizing linear Boolean functions (Q3186844) (← links)
- Circuit Complexity Meets Ontology-Based Data Access (Q3194705) (← links)
- Smallest Formulas for Parity of 2 k Variables Are Essentially Unique (Q3511317) (← links)
