Mobin Yahyazadeh

Mobin Yahyazadeh
Are you Mobin Yahyazadeh?

Claim your profile, edit publications, add additional information:

Contact Details

Name
Mobin Yahyazadeh
Affiliation
Location

Pubs By Year

Pub Categories

 
Computer Science - Data Structures and Algorithms (1)
 
Computer Science - Computational Complexity (1)

Publications Authored By Mobin Yahyazadeh

In the communication problem $\mathbf{UR}$ (universal relation) [KRW95], Alice and Bob respectively receive $x, y \in\{0,1\}^n$ with the promise that $x\neq y$. The last player to receive a message must output an index $i$ such that $x_i\neq y_i$. We prove that the randomized one-way communication complexity of this problem in the public coin model is exactly $\Theta(\min\{n,\log(1/\delta)\log^2(\frac n{\log(1/\delta)})\})$ for failure probability $\delta$. Read More