Pages that link to "Item:Q3722415"
From MaRDI portal
The following pages link to The complexity of promise problems with applications to public-key cryptography (Q3722415):
Displaying 50 items.
- A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes (Q294649) (← links)
- A thirty year old conjecture about promise problems (Q347124) (← links)
- Randomness buys depth for approximate counting (Q483707) (← links)
- A framework for non-interactive instance-dependent commitment schemes (NIC) (Q500985) (← links)
- Promise problems solved by quantum and classical finite automata (Q511009) (← links)
- Quantum finite automata: advances on Bertoni's ideas (Q517033) (← links)
- Compactly representing utility functions using weighted goals and the Max aggregator (Q622111) (← links)
- The shrinking property for NP and coNP (Q627189) (← links)
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds (Q645124) (← links)
- Inseparability and strong hypotheses for disjoint NP pairs (Q693061) (← links)
- On the complexity of entailment in existential conjunctive first-order logic with atomic negation (Q714500) (← links)
- NP is as easy as detecting unique solutions (Q1090454) (← links)
- Promise problems complete for complexity classes (Q1109568) (← links)
- Unambiguous computations and locally definable acceptance types (Q1127545) (← links)
- Practic zero-knowledge proofs: Giving hints and using deficiencies (Q1180509) (← links)
- Separating complexity classes with tally oracles (Q1185002) (← links)
- Graph isomorphism is low for PP (Q1210331) (← links)
- A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm (Q1261018) (← links)
- Hard promise problems and nonuniform complexity (Q1261468) (← links)
- A relation of primal--dual lattices and the complexity of shortest lattice vector problem (Q1274988) (← links)
- A hierarchy based on output multiplicity (Q1274991) (← links)
- A taxonomy of complexity classes of functions (Q1329166) (← links)
- On the limits of nonapproximability of lattice problems (Q1577010) (← links)
- A note on the non-NP-hardness of approximate lattice problems under general Cook reductions. (Q1589481) (← links)
- On the reducibility of sets inside NP to sets with low information content (Q1765294) (← links)
- A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor (Q1861566) (← links)
- Mathematical problems in cryptology (Q1910812) (← links)
- On membership comparable sets (Q1961377) (← links)
- Parallelization of entanglement-resistant multi-prover interactive proofs (Q2015158) (← links)
- Evaluation of exact quantum query complexities by semidefinite programming (Q2100824) (← links)
- Understanding PPA-completeness (Q2208253) (← links)
- Revisiting Deutsch-Jozsa algorithm (Q2216118) (← links)
- On the relationship between statistical zero-knowledge and statistical randomized encodings (Q2281251) (← links)
- An oracle separating conjectures about incompleteness in the finite domain (Q2290649) (← links)
- Reductions between disjoint NP-pairs (Q2387199) (← links)
- Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs (Q2407103) (← links)
- On the complexity of restoring corrupted colorings (Q2424718) (← links)
- Modeling time criticality of information (Q2445406) (← links)
- Graph Isomorphism is in SPP (Q2495656) (← links)
- How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge (Q2516524) (← links)
- A common algebraic description for probabilistic and quantum computations (Q2575744) (← links)
- On the Relationship Between Statistical Zero-Knowledge and Statistical Randomized Encodings (Q2829956) (← links)
- Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete (Q2954372) (← links)
- Simplified Derandomization of BPP Using a Hitting Set Generator (Q3088176) (← links)
- On the Average-Case Complexity of Property Testing (Q3088183) (← links)
- In a World of P=BPP (Q3088186) (← links)
- On the Complexity of Computational Problems Regarding Distributions (Q3088193) (← links)
- Introduction to Testing Graph Properties (Q3088198) (← links)
- Contemplations on Testing Graph Properties (Q3088201) (← links)
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets (Q3210177) (← links)
