Name
Abstract | ||
|---|---|---|
We give a simple information theoretic proof that the public-coin randomized communication complexity of the greater-than function is Omega(log n) for bit-strings of length n. |
Year | Venue | Field |
|---|---|---|
2015 | 2015 53RD ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON) | Complexity class,Quantum complexity theory,Discrete mathematics,Average-case complexity,Structural complexity theory,Parameterized complexity,Computer science,Theoretical computer science,Communication complexity,Descriptive complexity theory,Worst-case complexity |
DocType | ISSN | Citations |
Conference | 2474-0195 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sivaramakrishnan Natarajan Ramamoorthy | 1 | 9 | 2.92 |
| Makrand Sinha | 2 | 12 | 3.67 |