scientific article; zbMATH DE number 7650418

DOI10.4230/LIPIcs.ITCS.2020.70MaRDI QIDQ5875777

Rahul Santhanam, Ján Pich, Igor C. Oliveira, Shuichi Hirahara, Ninad Rajgopal, Lijie Chen

Publication date: 3 February 2023

Full work available at URL: https://arxiv.org/abs/1911.08297

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

circuit lower boundsminimum circuit size problemnatural proofshardness magnification

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (4)

Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Unnamed Item ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Lower bounds and hardness magnification for sublinear-time shrinking cellular automata

This page was built for publication: