Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (Q301524): Difference between revisions

@@ 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/s00037-016-0128-9
+Normal rank
@@ Property / OpenAlex ID @@
+W2336471965
@@ Property / OpenAlex ID: W2336471965 / rank @@
+Normal rank
@@ Property / cites work @@
+\(\Sigma_ 1^ 1\)-formulae on finite structures
@@ Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank @@
+Normal rank
@@ Property / cites work @@
+From Secrecy to Soundness: Efficient Verification via Secure Computation
+Normal rank
@@ Property / cites work @@
+Encoding Functions with Constant Online Rate or How to Compress Garbled Circuits Keys
+Normal rank
@@ Property / cites work @@
+Pseudorandomness when the odds are against you
@@ Property / cites work: Pseudorandomness when the odds are against you / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators with optimal seed length for non-boolean poly-size circuits
+Normal rank
@@ Property / cites work @@
+\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
+Normal rank
@@ Property / cites work @@
+Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
+Normal rank
@@ Property / cites work @@
+Derandomization in Cryptography
@@ Property / cites work: Derandomization in Cryptography / rank @@
+Normal rank
@@ Property / cites work @@
+Uniform generation of NP-witnesses using an NP-oracle
+Normal rank
@@ Property / cites work @@
+Q3152800
@@ Property / cites work: Q3152800 / rank @@
+Normal rank
@@ Property / cites work @@
+On problems without polynomial kernels
@@ Property / cites work: On problems without polynomial kernels / rank @@
+Normal rank
@@ Property / cites work @@
+Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
+Normal rank
@@ Property / cites work @@
+Improved Delegation of Computation Using Fully Homomorphic Encryption
+Normal rank
@@ Property / cites work @@
+Leakage-Resilient Storage
@@ Property / cites work: Leakage-Resilient Storage / rank @@
+Normal rank
@@ Property / cites work @@
+Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
+Normal rank
@@ Property / cites work @@
+Random generation of combinatorial structures from a uniform distribution
+Normal rank
@@ Property / cites work @@
+On the randomness complexity of efficient sampling
+Normal rank
@@ Property / cites work @@
+Protecting Circuits from Computationally Bounded and Noisy Leakage
+Normal rank
@@ Property / cites work @@
+On the hardness of computing the permanent of random matrices
+Normal rank
@@ Property / cites work @@
+Infeasibility of instance compression and succinct PCPs for NP
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers
+Normal rank
@@ Property / cites work @@
+Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
+Normal rank
@@ Property / cites work @@
+Q4440439
@@ Property / cites work: Q4440439 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Local List Decoding
@@ Property / cites work: The Complexity of Local List Decoding / rank @@
+Normal rank
@@ Property / cites work @@
+Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
+Normal rank
@@ Property / cites work @@
+If NP languages are hard on the worst-case, then it is easy to find their hard instances
+Normal rank
@@ Property / cites work @@
+Worst-Case to Average-Case Reductions Revisited
@@ Property / cites work: Worst-Case to Average-Case Reductions Revisited / rank @@
+Normal rank
@@ Property / cites work @@
+On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+Randomness vs time: Derandomization under a uniform assumption
+Normal rank
@@ Property / cites work @@
+How to delegate computations
@@ Property / cites work: How to delegate computations / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+Q3210157
@@ Property / cites work: Q3210157 / rank @@
+Normal rank
@@ Property / cites work @@
+Impossibility Results on Weakly Black-Box Hardness Amplification
+Normal rank
@@ Property / cites work @@
+On the Complexity of Hardness Amplification
@@ Property / cites work: On the Complexity of Hardness Amplification / rank @@
+Normal rank
@@ Property / cites work @@
+Derandomizing Arthur-Merlin games using hitting sets
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+th Conference on Computational Complexity (CCC 2015)
+Normal rank
@@ Property / cites work @@
+An Introduction to Randomness Extractors
@@ Property / cites work: An Introduction to Randomness Extractors / rank @@
+Normal rank
@@ Property / cites work @@
+Weak derandomization of weak algorithms: explicit versions of Yao's lemma
+Normal rank
@@ Property / cites work @@
+Simple extractors for all min-entropies and a new pseudorandom generator
+Normal rank
@@ Property / cites work @@
+Pseudorandomness for approximate counting and sampling
+Normal rank
@@ Property / cites work @@
+Low-End Uniform Hardness versus Randomness Tradeoffs for AM
+Normal rank
@@ Property / cites work @@
+Hardness Amplification Proofs Require Majority
@@ Property / cites work: Hardness Amplification Proofs Require Majority / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators without the XOR lemma
@@ Property / cites work: Pseudorandom generators without the XOR lemma / rank @@
+Normal rank
@@ Property / cites work @@
+Extractor Codes
@@ Property / cites work: Extractor Codes / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandomness and average-case complexity via uniform reductions
+Normal rank
@@ Property / cites work @@
+Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
+Normal rank
@@ Property / cites work @@
+The complexity of constructing pseudorandom generators from hard functions
+Normal rank