Loading jsMath...
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