Easiness amplification and uniform circuit lower bounds

DOI10.4230/LIPICS.CCC.2017.8MaRDI QIDQ5111138zbMATH OpenFDO

Authors Cody D. Murray, Ryan Williams

Publication date 26 May 2020

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2017.8

zbMATH Keywords

amplificationnon-relativizingspace complexitytime complexityuniform circuit complexity

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On uniformity and circuit lower bounds
• Amplifying circuit lower bounds against polynomial time, with applications
• Amplifying lower bounds by means of self-reducibility
• Non-uniform depth of polynomial time and space simulations.
• Lower bounds against weakly uniform circuits

Cited in

(4)

• Amplifying circuit lower bounds against polynomial time, with applications
• On uniformity and circuit lower bounds
• Non-uniform depth of polynomial time and space simulations.
• Simulating time with square-root space

This page was built for publication: Easiness amplification and uniform circuit lower bounds

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