Combinatorial characterization of read-once formulae

DOI10.1016/0012-365X(93)90372-ZzbMATH0781.06012OpenAlexW2029376824WikidataQ127725709MaRDI QIDQ685684FDOQ685684

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

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

zbMATH Keywords

combinatorial optimizationread-once functionsformula sizenumber of variables

Mathematics Subject Classification ID

Boolean functions (06E30)

Recommendations

• scientific article; zbMATH DE number 176867
• How Do Read-Once Formulae Shrink?
• Functions that are read-once on a subset of their inputs

Cites work

• scientific article; zbMATH DE number 3819502 (Why is no real title available?)
• scientific article; zbMATH DE number 3545568 (Why is no real title available?)
• A note on the production of matroid minors
• Anti-blocking polyhedra
• Bottleneck extrema
• The Forbidden Minors of Binary Clutters

Cited in

(26)

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

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)