Paper Info
Title
The Direct Sum of Universal Relations.
Abstract
•We consider the direct-sum question for the universal relation.•We show that solving m instances needs m⋅(n−O(log⁡m)) bits using an information-theoretic argument.•We describe a newer bound of m⋅(n−1)−1 due to Alexander Kozachinsky using a rank argument.
Year
DOI
Venue
2018
10.1016/j.ipl.2018.04.009
Information Processing Letters
Keywords
DocType
Volume
Direct sum,Universal relation,Communication complexity,Karchmer–Wigderson relations,Computational complexity
Journal
136
ISSN
Citations 
PageRank 
0020-0190
0
0.34
References 
Authors
6
1
Name
Order
Citations
PageRank
Or Meir16610.47