Marginal hitting sets imply super-polynomial lower bounds for permanent

DOI10.1145/2090236.2090275zbMath1347.68161OpenAlexW2072311401MaRDI QIDQ2826080

Maurice Jansen, Rahul Santhanam

Publication date: 7 October 2016

Published in: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2090236.2090275

zbMATH Keywords

lower boundspermanentderandomizationarithmetic circuitspolynomial identity testingcomputational complexity theory

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) Randomized algorithms (68W20)

Related Items (3)

Derandomization from Algebraic Hardness ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ Unifying known lower bounds via geometric complexity theory

Cites Work

• Unnamed Item
• The reproducible properties of correct forecasts
• The dimensions of individual strings and sequences
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• The Complexity of Forecast Testing
• The Well-Calibrated Bayesian
• Asymptotic calibration
• Dimension in Complexity Classes
• Universal prediction
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES

This page was built for publication: Marginal hitting sets imply super-polynomial lower bounds for permanent