Pages that link to "Item:Q1813126"
From MaRDI portal
The following pages link to The gap between monotone and non-monotone circuit complexity is exponential (Q1813126):
Displaying 25 items.
- On derandomization and average-case complexity of monotone functions (Q428873) (← links)
- An axiomatic duality framework for the theta body and related convex corners (Q517307) (← links)
- Negation-limited circuit complexity of symmetric functions (Q671626) (← links)
- A note on the power of majority gates and modular gates (Q673905) (← links)
- A lower bound for intuitionistic logic (Q876385) (← links)
- One-way permutations, computational asymmetry and distortion. (Q959774) (← links)
- On the minimum number of negations leading to super-polynomial savings (Q1029051) (← links)
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits (Q1566723) (← links)
- An exponential gap with the removal of one negation gate (Q1603543) (← links)
- On the negation-limited circuit complexity of merging (Q1861565) (← links)
- Monotone simulations of non-monotone proofs. (Q1872729) (← links)
- Valiant's holant theorem and matchgate tensors (Q2382280) (← 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)
- Acyclicity programming for sigma-protocols (Q2695643) (← links)
- $$P\mathop{ =}\limits^{?}NP$$ (Q2826803) (← links)
- On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography (Q3179494) (← links)
- (Q4612482) (← links)
- (Q4638077) (← links)
- (Q5060749) (← links)
- A recursion-theoretic characterisation of the positive polynomial-time functions (Q5079742) (← 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)
- (Q5140848) (← links)
