The isomorphism conjecture for constant depth reductions

DOI10.1016/j.jcss.2010.06.003zbMath1214.68169OpenAlexW2021469124WikidataQ123256973 ScholiaQ123256973MaRDI QIDQ619896

Manindra Agrawal

Publication date: 18 January 2011

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.06.003

zbMATH Keywords

complete setsisomorphism conjectureconstant depth circuits

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)

Related Items (4)

The minimum oracle circuit size problem ⋮ Local restrictions from the Furst-Saxe-Sipser paper ⋮ Unnamed Item ⋮ Investigations Concerning the Structure of Complete Sets

Cites Work

• Unnamed Item
• Unnamed Item
• Rudimentary reductions revisited
• Space-bounded reducibility among combinatorial problems
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Hardness vs randomness
• The complexity of iterated multiplication
• On the isomorphism conjecture for weak reducibilities
• On uniformity within \(NC^ 1\)
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Intersection Theorems for Systems of Sets
• Parity, circuits, and the polynomial-time hierarchy
• Constant Depth Reducibility
• Languages that Capture Complexity Classes
• Simple Constructions of Almost k-wise Independent Random Variables
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• A First-Order Isomorphism Theorem
• The isomorphism conjecture fails relative to a random oracle
• The Isomorphism Conjecture Holds Relative to an Oracle
• Reducing the complexity of reductions

This page was built for publication: The isomorphism conjecture for constant depth reductions