Reducing the complexity of reductions

DOI10.1007/S00037-001-8191-1MaRDI QIDQ5957724zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich

Publication date 5 May 2002

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-001-8191-1

zbMATH Keywords

Berman-Hartmanis conjecturepowering in finite fields

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 1559593
• scientific article; zbMATH DE number 2081095
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Polynomial-time isomorphism of 1-L-complete sets
• The isomorphism conjecture for NP

Cited in

(24)

• Rudimentary reductions revisited
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Local reduction
• Reducing sequences
• A reduction algorithm meeting users' requirements.
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Reductivity
• Non-uniform reductions
• Investigations concerning the structure of complete sets
• The Complexity of Complexity
• Nonuniform reductions and NP-completeness
• Local reductions
• DNF sparsification and a faster deterministic counting algorithm
• Finding Reductions Automatically
• scientific article; zbMATH DE number 1222831 (Why is no real title available?)
• Lazy narrowing with simplification
• scientific article; zbMATH DE number 1559593 (Why is no real title available?)
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• Local restrictions from the Furst-Saxe-Sipser paper
• Strong Reductions and Isomorphism of Complete Sets
• Improved pseudorandom generators from pseudorandom multi-switching lemmas
• The isomorphism conjecture for constant depth reductions
• Kolmogorov complexity characterizes statistical zero knowledge
• Comparing reductions to NP-complete sets

This page was built for publication: Reducing the complexity of reductions

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