14 citations · 72 across the 43 of their papers we have counts for
Showing 2018 · cs.ITShow all
3 papers · 2 filters
cs.IT2018★ 4 cited
Guessing with a Bit of Help
Nir Weinberger, Ofer Shayevitz
What is the value of a single bit to a guesser? We study this problem in a setup where Alice wishes to guess an i.i.d. random vector, and can procure one bit of information from Bo…
cs.IT2018★ 11 cited
A Bound on the Shannon Capacity via a Linear Programming Variation
Sihuang Hu, Itzhak Tamo, Ofer Shayevitz
We prove an upper bound on the Shannon capacity of a graph via a linear programming variation. We show that our bound can outperform both the Lovász theta number and the Haemers mi…
cs.IT2018★ 1 cited
Shannon Capacity is Achievable for Binary Interactive First-Order Markovian Protocols
Assaf Ben-Yishai, Ofer Shayevitz, Young-Han Kim
We address the problem of simulating an arbitrary binary interactive first-order Markovian protocol over a pair of binary symmetric channels with crossover probability $\varepsilon…