Pages that link to "Item:Q1094870"
From MaRDI portal
The following pages link to The monotone circuit complexity of Boolean functions (Q1094870):
Displaying 50 items.
- Monotone real circuits are more powerful than monotone Boolean circuits (Q290209) (← links)
- Lower bounds for monotone counting circuits (Q313809) (← links)
- On sunflowers and matrix multiplication (Q354642) (← links)
- Towards NP-P via proof complexity and search (Q408544) (← links)
- Satisfiability, branch-width and Tseitin tautologies (Q430830) (← links)
- Cutting planes cannot approximate some integer programs (Q453048) (← links)
- Clique problem, cutting plane proofs and communication complexity (Q456115) (← links)
- Lower bounds for tropical circuits and dynamic programs (Q493653) (← links)
- \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits (Q626676) (← links)
- A sorting network in bounded arithmetic (Q638498) (← links)
- Negation-limited circuit complexity of symmetric functions (Q671626) (← links)
- A note on the power of majority gates and modular gates (Q673905) (← links)
- Lower bounds for monotone span programs (Q677989) (← links)
- On the power of small-depth threshold circuits (Q685717) (← links)
- Negation-limited formulas (Q729897) (← links)
- Replaceability and computational equivalence for monotone boolean functions (Q798296) (← links)
- The conjunctive complexity of quadratic Boolean functions (Q808253) (← links)
- Nondeterministic functions and the existence of optimal proof systems (Q837177) (← links)
- Limiting negations in non-deterministic circuits (Q837192) (← links)
- A lower bound for intuitionistic logic (Q876385) (← links)
- Very large cliques are easy to detect (Q932700) (← links)
- Resolution over linear equations and multilinear proofs (Q952492) (← links)
- One-way permutations, computational asymmetry and distortion. (Q959774) (← links)
- Reductions for monotone Boolean circuits (Q959813) (← links)
- On the complexity of cutting-plane proofs using split cuts (Q969513) (← links)
- On lengths of proofs in non-classical logics (Q1006613) (← links)
- Substitution Frege and extended Frege proof systems in non-classical logics (Q1023047) (← links)
- Threshold functions and bounded depth monotone circuits (Q1088970) (← links)
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition (Q1095871) (← links)
- A lower bound for read-once-only branching programs (Q1107323) (← links)
- Entropy of contact circuits and lower bounds on their complexity (Q1109754) (← links)
- On monotone simulations on nonmonotone networks (Q1121853) (← links)
- Efficient monotone circuits for threshold functions (Q1122560) (← links)
- Lower bounds for depth-restricted branching programs (Q1173954) (← links)
- A simple lower bound for monotone clique using a communication game (Q1190521) (← links)
- An exponential lower bound for the size of monotone real circuits (Q1288204) (← links)
- On almost bad Boolean bases (Q1349706) (← links)
- Claw-free graphs---a survey (Q1356695) (← links)
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits (Q1566723) (← links)
- On the bottleneck counting argument (Q1566741) (← links)
- An exponential gap with the removal of one negation gate (Q1603543) (← links)
- Some complete and intermediate polynomials in algebraic complexity theory (Q1635814) (← links)
- Bounds for the average-case complexity of monotone Boolean functions (Q1675542) (← links)
- The gap between monotone and non-monotone circuit complexity is exponential (Q1813126) (← links)
- On the number of ANDs versus the number of ORs in monotone Boolean circuits (Q1847364) (← links)
- Monotone Boolean dualization is in co-NP\([\log^{2}n]\). (Q1853168) (← links)
- Lower bounds for the weak pigeonhole principle and random formulas beyond resolution (Q1854546) (← links)
- On the negation-limited circuit complexity of merging (Q1861565) (← links)
- Affine projections of symmetric polynomials. (Q1872730) (← links)
- On the automatizability of resolution and related propositional proof systems (Q1881219) (← links)
