scientific article; zbMATH DE number 176869
From MaRDI portal
Publication:4036700
zbMATH Open0766.68040MaRDI QIDQ4036700FDOQ4036700
Authors: Michael Sipser, Michelangelo Grigni 
Publication date: 18 May 1993
Title of this publication is not available (Why is that?)
Recommendations
complete problemsmonotone reducibilityBarrington's gadgetmonotone branching programmonotone complexity classesmonotone computation
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (22)
- Complexity of monotonic functions
- Positive versions of polynomial time
- Proof complexity of monotone branching programs
- Distributed Pseudorandom Functions for General Access Structures in NP
- Cutting-edge cryptography through the lens of secret sharing
- Degrees of monotone complexity
- Monotone separation of logarithmic space from logarithmic depth
- Secret Sharing for mNP: Completeness Results
- Complete problems for monotone NP
- Positive First-order Logic on Words and Graphs
- Secret-sharing for NP
- Cutting-Edge Cryptography Through the Lens of Secret Sharing
- A recursion-theoretic characterisation of the positive polynomial-time functions
- The splitting power of branching programs of bounded repetition and CNFs of bounded width
- Monotone measures of statistical complexity
- Depth lower bounds for monotone semi-unbounded fan-in circuits.
- CDS composition of multi-round protocols
- On the complexity of determinizing monitors
- Acyclicity programming for sigma-protocols
- Adventures in monotone complexity and TFNP
- Title not available (Why is that?)
- Monotone Boolean formulas can approximate monotone linear threshold functions
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036700)
