Showing cs.CCShow all
3 papers · 1 filter
cs.CC2018
From expanders to hitting distributions and simulation theorems
Alexander Kozachinskiy
Recently, Chattopadhyay et al. (\cite{chattopadhyay2017simulation}) proved that any gadget having so called \emph{hitting distributions} admits deterministic "query-to-communicatio…
cs.CC2018
Recognizing Read-Once Functions from Depth-Three Formulas
Alexander Kozachinskiy
Consider the following decision problem: for a given monotone Boolean function decide, whether is read-once. For this problem, it is essential how the input function is…
cs.CC2015
On Slepian--Wolf Theorem with Interaction
Alexander Kozachinskiy
In this paper we study interactive "one-shot" analogues of the classical Slepian-Wolf theorem. Alice receives a value of a random variable , Bob receives a value of another rand…