Circuit lower bounds for MCSP from local pseudorandom generators

DOI10.4230/LIPICS.ICALP.2019.39MaRDI QIDQ5091189zbMATH OpenFDO

Authors Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

Publication date 21 July 2022

zbMATH Keywords

constant-depth circuitsbranching programscircuit 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)

Recommendations

• Circuit lower bounds for MCSP from local pseudorandom generators
• On the average-case complexity of MCSP and its variants
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• On the (non) NP-hardness of computing circuit complexity
• On the NP-Completeness of the Minimum Circuit Size Problem.

Cites work

• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 1834654 (Why is no real title available?)
• scientific article; zbMATH DE number 7250141 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Circuit minimization problem
• Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
• Formula lower bounds via the quantum method
• On the average-case complexity of MCSP and its variants
• Power from Random Strings
• Pseudorandomness from shrinkage
• Randomness is linear in space
• The Shrinkage Exponent of de Morgan Formulas is 2
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity

Cited in

(5)

• MCSP is hard for read-once nondeterministic branching programs
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
• Circuit lower bounds for MCSP from local pseudorandom generators
• One-tape Turing machine and branching program lower bounds for MCSP

This page was built for publication: Circuit lower bounds for MCSP from local pseudorandom generators

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