Instance-wise hardness and refutation versus derandomization for Arthur-Merlin protocols

DOI10.1007/S00037-025-00279-2MaRDI QIDQ6892817zbMATH OpenFDO

Authors Dieter Van Melkebeek, Nicollas Mocelin Sdroievski

Publication date 28 November 2025

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00037-025-00279-2

zbMATH Keywords

Arthur-Merlin protocolderandomizationinstance-wise hardnessrandomnesstargeted hitting-set generator

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Cites work

• BPP has subexponential time simulations unless EXPTIME has publishable proofs
• Arthur and Merlin as oracles
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Characterizing derandomization through hardness of Levin-Kolmogorov complexity
• Delegating computation: interactive proofs for muggles
• Derandomization from time-space tradeoffs
• Derandomization vs refutation: a unified framework for characterizing derandomization
• Derandomizing Arthur-Merlin games under uniform assumptions
• Derandomizing Arthur-Merlin games using hitting sets
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Hardness vs randomness
• Hardness vs randomness, revised: uniform, non-black-box, and instance-wise
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• In a world of \(\mathrm{P}=\mathrm{BPP}\)
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Instance-wise hardness versus randomness tradeoffs for Arthur-Merlin protocols
• Linear-time encodable and decodable error-correcting codes
• Low-End Uniform Hardness versus Randomness Tradeoffs for AM
• Natural proofs versus derandomization
• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
• On doubly-efficient interactive proof systems
• On exponential-time hypotheses, derandomization, and circuit lower bounds (extended abstract)
• On the complexity of decoding Reed-Solomon codes (Corresp.)
• Pseudo-random generators for all hardnesses
• Pseudorandomness and average-case complexity via uniform reductions
• Randomness vs time: Derandomization under a uniform assumption
• Simple extractors for all min-entropies and a new pseudorandom generator
• Two Comments on Targeted Canonical Derandomizers
• Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
• Unstructured hardness to average-case randomness

This page was built for publication: Instance-wise hardness and refutation versus derandomization for Arthur-Merlin protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6892817)