scientific article; zbMATH DE number 7150624

MaRDI QIDQ5207889zbMATH OpenFDO

Authors Mrinal Kumar, Ramprasad Saptharishi

Publication date 13 January 2020

Full work available at URL http://bulletin.eatcs.org/index.php/beatcs/article/view/591/599

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 7561765
• Derandomization from Algebraic Hardness
• Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes
• Hardness-randomness tradeoffs for bounded depth arithmetic circuits
• scientific article; zbMATH DE number 7250153
• scientific article; zbMATH DE number 3936520
• Publication:3197949
• Hardness hypotheses, derandomization, and circuit complexity
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Computational Randomness from Generalized Hardcore Sets

Cited in

(9)

• Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes
• Factorization of polynomials given by arithmetic branching programs
• scientific article; zbMATH DE number 5044336 (Why is no real title available?)
• Progress on polynomial identity testing. II
• Factorization of polynomials given by arithmetic branching programs
• Lower bounds for the sum of small-size algebraic branching programs
• Hardness-randomness tradeoffs for bounded depth arithmetic circuits
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• scientific article; zbMATH DE number 7561765 (Why is no real title available?)

This page was built for publication:

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