Incompressible functions, relative-error extractors, and the power of nondeterministic reductions

DOI10.1007/s00037-016-0128-9zbMath1345.68126OpenAlexW2336471965MaRDI QIDQ301524

Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang

Publication date: 30 June 2016

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-016-0128-9

zbMATH Keywords

compressionpseudorandomnessextractorsnondeterministic reductions

Mathematics Subject Classification ID

Related Items (6)

The Journey from NP to TFNP Hardness ⋮ (Nondeterministic) hardness vs. non-malleability ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ Unnamed Item ⋮ Improved Extractors for Recognizable and Algebraic Sources ⋮ Placing conditional disclosure of secrets in the communication complexity universe

Cites Work

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

This page was built for publication: Incompressible functions, relative-error extractors, and the power of nondeterministic reductions