2 citations · 4 across the 4 of their papers we have counts for
4 papers · 1 filter
Searching Trees with Permanently Noisy Advice: Walking and Query Algorithms
Lucas Boczkowski, Uriel Feige, Amos Korman +1
We consider a search problem on trees in which the goal is to find an adversarially placed treasure, while relying on local, partial information. Specifically, each node in the tre…
Streaming Communication Protocols
Lucas Boczkowski, Iordanis Kerenidis, Frédéric Magniez
We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. We consider two agents that want to compute some function that…
Sensitivity of mixing times in Eulerian digraphs
Lucas Boczkowski, Yuval Peres, Perla Sousi
Let be a lazy random walk on a graph . If is undirected, then the mixing time is upper bounded by the maximum hitting time of the graph. This fails for directed chains,…
Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits
Lucas Boczkowski, Amos Korman, Emanuele Natale
This paper considers the basic model of communication, in which in each round, each agent extracts information from few randomly chosen agents. We seek to identify…