Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

DOI10.1145/3404860zbMath1499.68102OpenAlexW3044440032MaRDI QIDQ5053073

Dimitrios Myrisiotis, Valentine Kabanets, Mahdi Cheraghchi, Zhenjian Lu

Publication date: 5 December 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

branching programsconstant-depth circuitscircuit lower boundsde Morgan formulaslocal PRGsminimum circuit-size problem (MCSP)pseudorandom generators (PRGs)

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (3)

Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization

This page was built for publication: Circuit Lower Bounds for MCSP from Local Pseudorandom Generators