Pages that link to "Item:Q1071001"
From MaRDI portal
The following pages link to Lower bounds on monotone complexity of the logical permanent (Q1071001):
Displaying 42 items.
- On derandomization and average-case complexity of monotone functions (Q428873) (← links)
- Lower bounds for tropical circuits and dynamic programs (Q493653) (← links)
- A note on the power of majority gates and modular gates (Q673905) (← links)
- On the computational complexity of qualitative coalitional games (Q814613) (← links)
- One-way permutations, computational asymmetry and distortion. (Q959774) (← links)
- On the minimum number of negations leading to super-polynomial savings (Q1029051) (← links)
- More on the complexity of slice functions (Q1079365) (← links)
- The complexity of central slice functions (Q1084375) (← links)
- Entropy of contact circuits and lower bounds on their complexity (Q1109754) (← links)
- A method for obtaining efficient lower bounds for monotone complexity (Q1112792) (← links)
- On monotone simulations on nonmonotone networks (Q1121853) (← links)
- Lower bounds for depth-restricted branching programs (Q1173954) (← links)
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\) (Q1178711) (← links)
- Expressing combinatorial optimization problems by linear programs (Q1186549) (← links)
- A simple lower bound for monotone clique using a communication game (Q1190521) (← links)
- Matching theory -- a sampler: From Dénes König to the present (Q1198643) (← links)
- Separating complexity classes related to \(\Omega\)-decision trees (Q1202936) (← links)
- A lower bound for monotone arithmetic circuits computing \(0-1\) permanent (Q1276316) (← links)
- Positive versions of polynomial time (Q1281503) (← links)
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits (Q1566723) (← links)
- Some complete and intermediate polynomials in algebraic complexity theory (Q1635814) (← links)
- The gap between monotone and non-monotone circuit complexity is exponential (Q1813126) (← links)
- Coxeter groups and nonuniform complexity (Q1814266) (← links)
- \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice (Q1904667) (← links)
- Circuit complexity of linear functions: gate elimination and feeble security (Q1946842) (← links)
- Proof complexity of monotone branching programs (Q2104254) (← links)
- On digraph coloring problems and treewidth duality (Q2427534) (← links)
- On algorithm complexity (Q2453388) (← links)
- Lower bounds for Boolean circuits of bounded negation width (Q2672949) (← links)
- Acyclicity programming for sigma-protocols (Q2695643) (← links)
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT (Q3398315) (← links)
- On Negations in Boolean Networks (Q3644711) (← links)
- Notes on Hazard-Free Circuits (Q4986809) (← links)
- Adventures in monotone complexity and TFNP (Q5090415) (← links)
- Lower Bounds for DeMorgan Circuits of Bounded Negation Width (Q5090491) (← links)
- A super-quadratic lower bound for depth four arithmetic circuits (Q5092474) (← links)
- Approximation Limitations of Pure Dynamic Programming (Q5216795) (← links)
- Natural proofs (Q5906823) (← links)
- Average circuit depth and average communication complexity (Q6102294) (← links)
- Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits (Q6567780) (← links)
- Localizability of the approximation method (Q6624428) (← links)
- Notes on Boolean read-\(k\) and multilinear circuits (Q6648273) (← links)
