scientific article; zbMATH DE number 7561532

DOI10.4230/LIPIcs.ICALP.2019.39zbMath1499.68101MaRDI QIDQ5091189

Valentine Kabanets, Mahdi Cheraghchi, Dimitrios Myrisiotis, Zhenjian Lu

Publication date: 21 July 2022

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

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)

MCSP is hard for read-once nondeterministic branching programs ⋮ Unnamed Item ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates

Cites Work

• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Randomness is linear in space
• Circuit minimization problem
• The Shrinkage Exponent of de Morgan Formulas is 2
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Formula lower bounds via the quantum method
• Pseudorandomness from Shrinkage
• Power from Random Strings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: