Sharp threshold results for computational complexity

DOI10.1145/3357713.3384283MaRDI QIDQ5145017zbMATH OpenOpenAlexFDO

Authors Lijie Chen, Ce Jin, Ryan Williams

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3357713.3384283

zbMATH Keywords

De Morgan formulasquantified derandomizationhardness magnification

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(9)

• On hitting-set generators for polynomials that vanish rarely
• Sharp separation and applications to exact and parameterized algorithms
• Constructive separations and their consequences
• Algorithms and lower bounds for comparator circuits from shrinkage
• Shiner–Davison–Landsberg complexity revisited
• Quantified Derandomization: How to Find Water in the Ocean
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
• Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms

This page was built for publication: Sharp threshold results for computational complexity

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