Characterization and Lower Bounds for Branching Program Size Using Projective Dimension.

DOI10.4230/LIPIcs.FSTTCS.2016.37zbMath1391.68040arXiv1604.07200OpenAlexW2927838217MaRDI QIDQ4636585

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

Publication date: 19 April 2018

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

zbMATH Keywords

projective dimensionlower boundsbranching program size

Mathematics Subject Classification ID

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

This page was built for publication: Characterization and Lower Bounds for Branching Program Size Using Projective Dimension.