Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BIPARTITE FORMULA COMPLEXITY:
Reports tagged with bipartite formula complexity:
TR16-181 | 15th November 2016
Avishay Tal

The Bipartite Formula Complexity of Inner-Product is Quadratic

A bipartite formula on binary variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves may compute any function of either the $x$ or $y$ variables. We show that any bipartite formula for the Inner-Product ... more >>>




ISSN 1433-8092 | Imprint