Characterization and lower bounds for branching program size using projective dimension

DOI10.1145/3305274MaRDI QIDQ5205793zbMATH OpenOpenAlexWikidataFDO

Authors Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma M. N.

Publication date 16 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2016/6872/

zbMATH Keywords

branching programslower boundsprojective dimension

Mathematics Subject Classification ID

Boolean functions (06E30) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Characterization and Lower Bounds for Branching Program Size Using Projective Dimension.
• Stochastic Algorithms: Foundations and Applications
• On Nečiporuk's theorem for branching programs
• scientific article; zbMATH DE number 3919835
• scientific article; zbMATH DE number 5899238

Cited in

(2)

• Characterization and Lower Bounds for Branching Program Size Using Projective Dimension.
• scientific article; zbMATH DE number 1408348 (Why is no real title available?)

This page was built for publication: Characterization and lower bounds for branching program size using projective dimension

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