2 papers
cs.CC2013
One-Round Multi-Party Communication Complexity of Distinguishing Sums
Daniel Apon, Jonathan Katz, Alex J. Malozemoff
We consider an instance of the following problem: Parties P_1,..., P_k each receive an input x_i, and a coordinator (distinct from each of these parties) wishes to compute f(x_1,..…
cs.CC2013
On Lower Bound Methods for Tree-like Cutting Plane Proofs
Daniel Apon
In the book Boolean Function Complexity by Stasys Jukna, two lower bound techniques for Tree-like Cutting Plane proofs (henceforth, "Tree-CP proofs") using Karchmer-Widgerson type…