Recognizing read-once functions from depth-three formulas

DOI10.1007/978-3-319-90530-3_20zbMath1434.68200arXiv1802.03815OpenAlexW2962829094WikidataQ128074554 ScholiaQ128074554MaRDI QIDQ5915579

Alexander Kozachinskiy

Publication date: 28 November 2018

Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenessmonotone Boolean functionscoNP-completenessread-once functionsdepth-three formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)

Related Items (2)

Testing read-once functions in a median-augmented element basis ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the readability of monotone Boolean formulae
• An improvement on the complexity of factoring read-once Boolean functions
• A New Approach to the Sensitivity Conjecture

This page was built for publication: Recognizing read-once functions from depth-three formulas