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

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

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

(14)

• Factorization of polynomials given by arithmetic branching programs
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Progress on polynomial identity testing. II
• Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes
• Hardness-randomness tradeoffs for bounded depth arithmetic circuits
• Factorization of polynomials given by arithmetic branching programs
• scientific article; zbMATH DE number 7561765 (Why is no real title available?)
• scientific article; zbMATH DE number 5044336 (Why is no real title available?)
• Lower bounds for the sum of small-size algebraic branching programs
• On matrix multiplication and polynomial identity testing
• Superpolynomial lower bounds against low-depth algebraic circuits
• Towards identity testing for sums of products of Read-once and multilinear bounded-Read formulae
• Lower bounds for the sum of small-size algebraic branching programs
• Explicit commutative ROABPs from partial derivatives

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)