On Improved Degree Lower Bounds for Polynomial Approximation.

DOI10.4230/LIPIcs.FSTTCS.2013.201zbMath1359.68077OpenAlexW1585240433MaRDI QIDQ2963913

Srikanth Srinivasan

Publication date: 21 February 2017

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2013/4373/pdf/14.pdf

zbMATH Keywords

approximationpolynomialscompressioncircuit lower bounds

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Unnamed Item ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates

This page was built for publication: On Improved Degree Lower Bounds for Polynomial Approximation.