The polynomial method in circuit complexity applied to algorithm design (invited talk)

DOI10.4230/LIPICS.FSTTCS.2014.47MaRDI QIDQ3299223zbMATH OpenFDO

Authors Ryan Williams

Publication date 19 July 2020

Mathematics Subject Classification ID

General topics in the theory of algorithms (68W01) Networks and circuits as models of computation; circuit complexity (68Q06)

Recommendations

• More applications of the polynomial method to algorithm design
• scientific article; zbMATH DE number 176873
• On the complexity of partial derivatives
• scientific article; zbMATH DE number 522838
• Applications of matrix methods to the theory of lower bounds in computational complexity

Cited in

(13)

• Fast exact algorithms using Hadamard product of polynomials
• A robust version of Hegedűs's lemma, with applications
• scientific article; zbMATH DE number 7651219 (Why is no real title available?)
• scientific article; zbMATH DE number 7559066 (Why is no real title available?)
• Faster all-pairs shortest paths via circuit complexity
• More applications of the polynomial method to algorithm design
• scientific article; zbMATH DE number 817509 (Why is no real title available?)
• Cryptanalytic applications of the polynomial method for solving multivariate equation systems over \(\mathrm{GF}(2)\)
• Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
• Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
• From circuit complexity to faster all-pairs shortest paths
• A new coding-based algorithm for finding closest pair of vectors
• On the Probabilistic Degrees of Symmetric Boolean Functions

This page was built for publication: The polynomial method in circuit complexity applied to algorithm design (invited talk)

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