2-local random reductions to 3-valued functions

DOI10.1007/S00037-008-0245-1zbMATH Open1188.68147OpenAlexW2048635696MaRDI QIDQ2269002FDOQ2269002

N. V. Vinodchandran, Aduri Pavan

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

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

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)

Cited In (2)

• On the power of two-local random reductions
• Title not available (Why is that?)

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)