Combinatorial characterization of read-once formulae

DOI10.1016/0012-365X(93)90372-ZzbMATH Open0781.06012OpenAlexW2029376824WikidataQ127725709 ScholiaQ127725709MaRDI QIDQ685684FDOQ685684

Ilan Newman, Nathan Linial, Michael Saks, Mauricio Karchmer, A. Wigderson

Publication date: 24 October 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(93)90372-z

Recommendations

• scientific article
• Recognizing read-once functions from depth-three formulas
• How Do Read-Once Formulae Shrink?
• Functions that are read-once on a subset of their inputs
• Recognizing read-once functions from depth-three formulas

zbMATH Keywords

combinatorial optimizationread-once functionsformula sizenumber of variables

Mathematics Subject Classification ID

Boolean functions (06E30)

Cites Work

• A note on the production of matroid minors
• Bottleneck extrema
• Title not available (Why is that?)
• Anti-blocking polyhedra
• Title not available (Why is that?)
• The Forbidden Minors of Binary Clutters

Cited In (25)

• Functions that are read-once on a subset of their inputs
• On effectivity functions of game forms
• Title not available (Why is that?)
• Characterizing arithmetic read-once formulae
• A global parallel algorithm for the hypergraph transversal problem
• Acyclic, or totally tight, two-person game forms: characterization and main properties
• Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
• Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
• Decision lists and related Boolean functions
• Building above read-once polynomials: identity testing and hardness of representation
• On the Expressive Power of Read-Once Determinants
• A note on monotone complexity and the rank of matrices
• Critical properties and complexity measures of read-once Boolean functions
• Read-Once Functions Revisited and the Readability Number of a Boolean Function
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs
• The read once formula of a series-parallel network
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems
• Competitive evaluation of threshold functions in the priced information model
• Read-once polynomial identity testing
• Sandwich problem for \(\varPi\)- and \(\varDelta\)-free multigraphs and its applications to positional games
• Decomposing complete edge-chromatic graphs and hypergraphs. Revisited
• Double Horn functions
• Using relevance queries for identification of read-once functions
• Theory revision with queries: Horn, read-once, and parity formulas

This page was built for publication: Combinatorial characterization of read-once formulae

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