Succinct hitting sets and barriers to proving algebraic circuits lower bounds

DOI10.1145/3055399.3055496zbMath1369.68240arXiv1701.05328OpenAlexW2583016001MaRDI QIDQ4978011

Amir Shpilka, Ben lee Volk, Michael A. Forbes

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1701.05328

zbMATH Keywords

barrierspolynomial identity testingalgebraic circuit complexitysuccinct hitting sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (5)

Barriers for Rank Methods in Arithmetic Complexity ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Unnamed Item ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ Unnamed Item

This page was built for publication: Succinct hitting sets and barriers to proving algebraic circuits lower bounds