We prove an optimal bound on the Shannon function $L(n,m,\epsilon)$ which describes the trade-off between the circuit-size complexity and the degree of approximation; that is $$L(n,m,\epsilon)\ =\ \Theta\left(\frac{m\epsilon^2}{\log(2 + m\epsilon^2)}\right)+O(n).$$ Our bound applies to any partial boolean function and any approximation degree, and thus completes the study of booleanfunction approximation, ... more >>>

Impagliazzo and Wigderson have recently shown that if there exists a decision problem solvable in time $2^{O(n)}$ and having circuit complexity $2^{\Omega(n)}$ (for all but finitely many $n$) then $\p=\bpp$. This result is a culmination of a series of works showing connections between the existence of hard predicates and the ... more >>>

In this note, we consider the problem of computing the coefficients of the characteristic polynomial of a given matrix, and the related problem of verifying the coefficents. Santha and Tan [CC98] show that verifying the determinant (the constant term in the characteristic polynomial) is complete for the class C=L, and ... more >>>

We prove that Polynomial Calculus and Polynomial Calculus with Resolution are not automatizable, unless W[P]-hard problems are fixed parameter tractable by one-side error randomized algorithms. This extends to Polynomial Calculus the analogous result obtained for Resolution by Alekhnovich and Razborov (SIAM J. Computing, 38(4), 2008). more >>>