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

DOI10.4230/LIPICS.FSTTCS.2014.47zbMATH Open1436.68392MaRDI QIDQ3299223FDOQ3299223

Authors: Ryan Williams 

Publication date: 19 July 2020

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

Mathematics Subject Classification ID

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

Cited In (13)

• Fast exact algorithms using Hadamard product of polynomials
• A robust version of Hegedűs's lemma, with applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Faster all-pairs shortest paths via circuit complexity
• More applications of the polynomial method to algorithm design
• Title not available (Why is that?)
• 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)