2 papers
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…