On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography (Q693058): Difference between revisions

@@ Property / author @@
-Alexander V. Smal
@@ Property / author: Alexander V. Smal / rank @@
-Normal rank
@@ Property / author @@
+Alexander V. Smal
@@ Property / author: Alexander V. Smal / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s00224-011-9354-3
+Normal rank
@@ Property / OpenAlex ID @@
+W1995485918
@@ Property / OpenAlex ID: W1995485918 / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom Generators in Propositional Proof Complexity
+Normal rank
@@ Property / cites work @@
+Average-Case Complexity
@@ Property / cites work: Average-Case Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Consequences of the provability of <i>NP</i> ⊆ <i>P</i>/<i>poly</i>
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+A Complete Public-Key Cryptosystem
@@ Property / cites work: A Complete Public-Key Cryptosystem / rank @@
+Normal rank
@@ Property / cites work @@
+An infinitely-often one-way function based on an average-case assumption
+Normal rank
@@ Property / cites work @@
+A Pseudorandom Generator from any One-way Function
+Normal rank
@@ Property / cites work @@
+On Robust Combiners for Oblivious Transfer and Other Primitives
+Normal rank
@@ Property / cites work @@
+Structural complexity of AvgBPP
@@ Property / cites work: Structural complexity of AvgBPP / rank @@
+Normal rank
@@ Property / cites work @@
+Propositional proof systems, the consistency of first order theories and the complexity of computations
+Normal rank
@@ Property / cites work @@
+On the weak pigeonhole principle
@@ Property / cites work: On the weak pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+Tautologies from Pseudo-Random Generators
@@ Property / cites work: Tautologies from Pseudo-Random Generators / rank @@
+Normal rank
@@ Property / cites work @@
+One way functions and pseudorandom generators
@@ Property / cites work: One way functions and pseudorandom generators / rank @@
+Normal rank
@@ Property / cites work @@
+Q4226453
@@ Property / cites work: Q4226453 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4251070
@@ Property / cites work: Q4251070 / rank @@
+Normal rank
@@ Property / cites work @@
+Speedup for natural problems and noncomputability
@@ Property / cites work: Speedup for natural problems and noncomputability / rank @@
+Normal rank
@@ Property / cites work @@
+On reducibility and symmetry of disjoint NP pairs.
+Normal rank
@@ Property / cites work @@
+Q4263798
@@ Property / cites work: Q4263798 / rank @@
+Normal rank