A Relation between the Protocol Partition Number and the Quasi-Additive Bound
classification
💻 cs.CC
keywords
programmingcomputinglinearnumberpartitionprotocolboundinteger
read the original abstract
In this note, we show that the linear programming for computing the quasi-additive bound of the formula size of a Boolean function presented by Ueno [MFCS'10] is equivalent to the dual problem of the linear programming relaxation of an integer programming for computing the protocol partition number. Together with the result of Ueno [MFCS'10], our results imply that there exists no gap between our integer programming for computing the protocol partition number and its linear programming relaxation.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.