2-local random reductions to 3-valued functions

DOI10.1007/S00037-008-0245-1MaRDI QIDQ2269002zbMATH OpenOpenAlexFDO

Authors Aduri Pavan, N. V. Vinodchandran

Publication date 15 March 2010

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-008-0245-1

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the power of two-local random reductions
• Locally random reductions: Improvements and applications
• The global power of additional queries to random oracles
• The power of adaptiveness and additional queries in random-self- reductions
• On the autoreducibility of functions

Cited in

(2)

• On the power of two-local random reductions
• scientific article; zbMATH DE number 697824 (Why is no real title available?)

This page was built for publication: 2-local random reductions to 3-valued functions

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